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.
  • The 3 *-order walks are recursively defined. I believe they are three specializations of DFS. See

—-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 —

  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 $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

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


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.

Morris in-order traversal running O(N), without extra storage is detailed. has explanations + full c++ code has C code has concise c code 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;
 	// 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) {
 		prev->right = cur; //create thread link
 		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
 		//prev->right = NULL; //optionally remove threadlink
		//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

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);

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.

binary search tree

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?