Sunday, September 18, 2011

Depth-First Binary Tree Traversal

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

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

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.Stack;

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

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

		Stack<Node> stack = new Stack<Node>();

		stack.push(root);

		Node current = null;

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

			if (current.left != null)
				stack.push(current.left);
			if (current.right != null)
				stack.push(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;
	}

}

5 comments:

  1. As per the definition of a DFS, shouldn't we push the right child of a node before the left child? So that when we pop, we first get the left child and we go through the entire left subtree before going to the right subtree?
    In your case, you are going over the right subtree before the left subtree.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. 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 Javascript Training in Chennai . or learn thru JavaScript Online Training India. Nowadays JavaScript has tons of job opportunities on various vertical industry.

      Delete
  2. either right first or left, IMHO - it will not effect time complexity O(~vertex) or space complexity O(~height)

    ReplyDelete