Here are my own “key” observations, possibly incomplete, on 5 standard tree walk algos, based on my book [[discrete math]]
- pre/in/post-order is defined for binary trees only. Why? in-order means “left-subtree, parent, right-subtree”, implying only 2 subtrees.
- In contrast, BFS/DFS are much more versatile. Their input can be any tree (binary etc) or other connected graphs. If not a tree, then BFS/DFS will *produce* a tree — you first choose a “root” node arbitrarily.
- The 3 *-order walks are recursively defined. I believe they are three specializations of DFS. See https://www.cs.bu.edu/teaching/c/tree/breadth-first/
—-That’s a tiny intro. Below are more advanced —
BFS uses an underlying queue. In contrast DFS is characterized by backtracking, which requires a stack. However, you can implement the queue/stack without recursion.
BFS feels like the most intuitive algo, recursion-free. Example — send a
mailer to all linkedin contacts:
# send to each direct contact
# send to each second-degree contacts …
DFS backtrack in my own language —
- # start at root.
- At each node, descend into first  subtree
- # descend until a leaf node A1
- # backtrack exactly one level up to B
- # descend into A1’s immediate next sibling A2’s family tree (if any) until a leaf node. If unable to move down (i.e. no A2), then move up to C.
Visually — if we assign a $val to each node such that these nodes form a BST, then we get the “shadow rule”. In-order DFS would probably visit the nodes in ascending order by $value
 the child nodes, of size 1 or higher, at each node must be remembered in some order.
I feel code is hard to write, as it’s hard to visualize or build the tree.
In-order walk must enter at root. If we only have the current node as the only input, then I assume there’s an uplink in each node. Here’s my algo:
Case 1: if i have Right child, then descend there and then descend Left all the way to a leaf node and return. Easy case.
Case 2: now we know i have no Right child. Am i a Left child? If yes then return my parent. Easy case.
Case 3: Now we know I am the Right child, without my own right child. This is the worst case. My left child (if any) is irrelevant, so effectively I am a leaf node. A right leaf node. Solution: Move up step by step. After the first up-right move, descend Left all the way.
For predecessor, I found this algo online, but it can’t move up so unable to support Case 2 and 3.
/* Find the inorder predecessor of current */
pre = current->left;
while (pre->right != NULL && pre->right != current)
pre = pre->right;
Based on that, here’s my successor algo:
/* Find the inorder sucessor of current */
pre = current->right;
while (pre->left != NULL && pre->left != current)
pre = pre->left;
This is a favorite algo interview topic.
- I believe in-order walk will print a binary search tree in left-to-right order.
- De-confuse — visiting is not same as printing. I believe we need to visit a node P to access its left child, but we must not print P so early!
- Binary tree is the only thing that uses in-order
- De-confuse — “node.parent” is not available. Singly-linked tree, not doubly-linked.
Is there a way to design an iterator over a binary search tree with the following properties?
1. Elements are visited in ascending order (i.e. an in-order traversal)
2. next() and hasNext() queries run in O(1) time.
3. Memory usage is O(1)
I feel O(1) memory is impossible since this is recursive (though all recursions can convert to iteration), with a stack data structure of size H := height of tree.
Similarly, hasNext() need to work through the stack of size H, so O(1) run time impossible
Morris may meet the requirement.
No expert here… Just a few pointers.
I feel binary heap is designed for a Subset of the “always-sorted” requirement on sorted trees. The subset is “yield the largest item on demand”.
Therefore, a binary heap is simpler (and faster) than a red-black tree.
As a solution, sorted data structures (like RB tree) are more in demand than priority queues (like heap). For example, the classic stock exchange order book is a sorted list, not a priority queue.
A priority queue hides all but the maximum node, so we don’t know how those nodes are physically stored.
#2) binary Heap — java priority queue
** note the left and right can be Swapped — No “shadow rule”. Not a BST. See http://tigertanbin2.blogspot.sg/2007/06/binary-search-tree.html
** used by schedulers in some kernels
#1) BST i.e. binary search tree
** simplest, almost naive
** left branch is completely “le” parent — the “shadow rule”
1b) red-black tree — best-known BST
defining property: any node to my left is smaller or equal. left child = parent. Both children is allowed to be equal to parent — binary search tree is completely unbiased.
The defining property defined visually: For each node, draw a vertical line (long shadow) through the tree.
* Left descendants’ v-lines are on or inside my v-line.
* Right descendants’ v-lines are on or outside my v-line.
When nodes move up or down the three, their shadows shift. I think this may help us visualize a BST successor, deletion and insertion.
the same group of items can build 2 different bs-trees, with different tree heights. How? The same entries could arrive out of sequence, just like IP packets.
The deeper the tree, the more iterations for a tree walk, the slower the sort.
Worst case bst has a tree height equal to input size, with one branch at each node?