# seek successor of a given node in a BST, with root node unkown

EPI300 Q14.2.

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.

1. `/* Find the inorder predecessor of current */`
2. `pre = current->left;`
3. `while (pre->right != NULL && pre->right != current)`
4. `   pre = pre->right;`

Based on that, here’s my successor algo:

1. `/* Find the inorder sucessor of current */`
2. `pre = current->right;`
3. `while (pre->left != NULL && pre->left != current)`
4. `   pre = pre->left;`

# binary tree in-order walk – my notes

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.

# BFS^DFS, pre^in^post-order

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 —

1. # start at root.
2. At each node, descend into first [1] subtree
3. # descend until a leaf node A1
4. # backtrack exactly one level up to B
5. # 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

[1] the child nodes, of size 1 or higher, at each node must be remembered in some order.

# Morris in-order traversal running O(N), without extra storage

http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html has concise c code

http://n00tc0d3r.blogspot.sg/2013/09/inorder-binary-tree-traversal-with.html has concise java implementation.

–threaded binary tree is the basis of Morris

The Morris algo need to construct the threaded BST, traverse and remove the extra links, all without recursion.

Assumption: no uplinks available.

MorrisInOrder.cpp is my c++ implementation with lots of instrumentation. Below is an earlier version:

–working C (not c++) code to traverse left to right:

```#include <cstdio>
#include <assert.h>
struct Node {
int val;
Node *left, *right;
Node(int x, Node * le = NULL, Node * ri = NULL) : val(x), left(le), right(ri) {}
};
void MorrisTraversal(Node * const root) { //no recursion, no stack, extra storate for 2 extra pointers
Node *cur = root;
while (cur != NULL) {
if (cur->left == NULL) { // cur is the lowest remaining value!
printf("%d \n", cur->val);
cur = cur->right;
continue;
}
// Now cur is not the lowest. Now locate predecessor and set prev to the predecessor.
// To construct a threaded BST, we will need to set prev->right to cur
// ( In a Backward traversal, we would find successor instead. )

Node * prev=cur->left; //purpose of prev: create/remove thread link prev->right=cur
for (; (prev->right != NULL && prev->right != cur); prev = prev->right) {}

printf("   %d is the predecessor of %d\n", prev->val, cur->val);

assert(cur->left != NULL);
if (prev->right == NULL) {
printf(" %d 's right child set to   %d\n", prev->val, cur->val);

// not ready to print cur, because cur has left child.
cur = cur->left;
prev = NULL; // optionally nullify prev as it is invalidated
}else{
//printf(" %d 's right thread link removed\n", prev->val);
printf("%d \n", cur->val);

//after printing cur, no need to move left. Must move right!
cur = cur->right;
prev = NULL; // optionally nullify prev as it is invalidated
}
}//while
printf("\n");
}

int main() {
// has this tree diagram
Node _1(1);
Node _3(3);
Node _2(2, &_1, &_3);
Node _4(4, &_2);
Node _7(7);
Node _9(9);
Node _8(8, &_7, &_9);
Node _6(6, NULL, &_8);
Node root(5, &_4, &_6);
MorrisTraversal(&root);
}

```

# binary tree in-order walk #bbg

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.

# binary heap vs red-black tree

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.

# most important binary trees

#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