Sunday, September 18, 2011

Breadth-First Binary Tree Traversal: Implementation & Complexity Analysis

For every element to be processed, we keep looping down till we reach the leaf child node. And then elements are processed while coming up.
Thus to process element n, we recursively loop (or loop to stack the elements) upto height of that node O(h)
Since going down by height, we divide the scope into half (left or right subtree) - O(h) is log n
And each time we loop (through recursion or stack) - a new layer of stack is allocated in memory

Time Complexity - O ( n log n )
Space Complexity - O ( n log n )

Thus for all elements -
Time & Space Complexity = nO(h) = nlog n = n log n

Any tree traversal - Inorder, PreOrder, PostOrder, BFS, DFS - are all same O(n log n)


import java.util.LinkedList;
import java.util.Queue;


public class BFSTreeTraversal {
	public void mirrorTreeWithOutRecursion(Node root) {

		Queue<Node> queue = new LinkedList<Node>();


		Node current = null;

		while (!queue.isEmpty()) {
			current = queue.poll();
			// do the processing on a node

			if (current.left != null)
			if (current.right != null)
	// process
	// example - here we are processing to create mirror of a tree
	public void process(Node n) {
		Node temp = n.left;
		n.left = n.right;
		n.right = temp;