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

  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.

Advertisements

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

http://www.quora.com/Why-does-the-Morris-in-order-traversal-algorithm-have-O-n-time-complexity is detailed.

https://codeoverflow.wordpress.com/tag/morris-inorder-traversal/ has explanations + full c++ code

http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ has C code

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

https://en.wikipedia.org/wiki/Threaded_binary_tree

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) {
 		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
 	}else{
 		//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
	}
 }//while
 printf("\n");
}

int main() {
	// https://en.wikipedia.org/wiki/Threaded_binary_tree#Non_recursive_Inorder_traversal_for_a_Threaded_Binary_Tree
	// 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.

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?