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.
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.
BFS uses an underlying queue (or something like a queue .. not too sure). In contrast DFS is characterized by backtracking, which requires a stack IMO. However, you can implement the queue/stack without recursion.
The 3 *-order walks are recursively defined.
BFS feels like the most intuitive algo, recursion-free. Example — send a
mailer to linkedin contacts.
# send to each direct contact
# send to each of my 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 $value to each node such that these nodes form a BST, then we get the “shadow rule”. 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.
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