Thursday, September 8, 2011

Construct a Tree from Inorder & Preorder traversals

This post is in continuation to my earlier post on Build a Binary Tree, given two traversals

The following procedure demonstrates on how to rebuild tree from given inorder and preorder traversals of a binary tree:

Logic -

  1. Preorder traversal visits Node, left subtree, right subtree recursively
  2. Inorder traversal visits left subtree, node, right subtree recursively
  3. Since we know that the first node in Preorder is its root, we can easily locate the root node in the inorder traversal and hence we can obtain left subtree and right subtree from the inorder traversal recursively

Consider the following example:

Preorder Traversal: 1 2 4 8 9 10 11 5 3 6 7

Inorder Traversal: 8 4 10 9 11 2 5 1 6 3 7

Iteration 1:

Root – {1}

Left Subtree – {8,4,10,9,11,2,5}

Right Subtree – {6,3,7}

Iteration 2:

Root – {2}
Left Subtree – {8,4,10,9,11}
Right Subtree – {5}

Root – {3}
Left Subtree – {6}
Right Subtree – {7}

...and so on...


Pseudo Code ::

	int preIdx = 0;

	buildTree (inOrder, preOrder, 0, in.length - 1)

	public Node buildTree (int[] in, int[] pre, int inStartIdx, int inEndIdx) {

		    // base case
		-> if(inStartIdx > inEndIdx)
			return null;
	
		-> Node n = new Node();
		-> n.data = pre[preIdx];
		-> preIdx++;
	
		// if start and end idx are equal - that means the node does not have any left or right child. 
		// We dont need to calculate .left and .right for this node and should return.


	
		-> if(inStartIdx == inEndIdx)
			return n;
	
		-> int inNodeIdx = findIdx(in, n.data)
	
		-> n.left = buildTree (in, pre, inStartIdx, inNodeIdx);
		-> n.right = buildTree (in, pre, inStartIdx + 1, inEndIdx);
	
		-> return n;

	}

References -

http://crackinterviewtoday.wordpress.com/2010/03/15/rebuild-a-binary-tree-from-inorder-and-preorder-traversals/
http://geeksforgeeks.org/archives/6633

1 comment:

  1. Hi Ashish

    Nice tutorial
    However Could you please check line 26 i think index you are sending as start is incorrect ?

    ReplyDelete