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)

package main.java.algo.datastructures.binarytree.traversal;

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

import main.java.algo.datastructures.binarytree.Node;

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

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

		queue.add(root);

		Node current = null;

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

			if (current.left != null)
				queue.add(current.left);
			if (current.right != null)
				queue.add(current.right);
		}
		return;
	}
	
	// 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;
	}

}

4 comments:

  1. Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Front end developer learn from JQuery Training . or learn thru ES6 Online Training India. Nowadays JavaScript has tons of job opportunities on various vertical industry.

    ReplyDelete
  2. Attend The Analytics Course in Bangalore From ExcelR. Practical Analytics Course in Bangalore Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Analytics Course in Bangalore.
    ExcelR Analytics Course in Bangalore

    ReplyDelete
  3. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    data analytics courses

    ReplyDelete