Objective: – Given a inorder and preorder traversal, construct a binary tree from that.
Input: Inorder and preorder traversals
Similar Problem: Construct a binary tree from given Inorder and Postorder Traversal
Approach:
int [] inOrder = {2,5,6,10,12,14,15};
int [] preOrder = {10,5,2,6,14,12,15};
- First element in preorder[] will be the root of the tree, here its 10.
- Now the search element 10 in inorder[], say you find it at position i, once you find it, make note of elements which are left to i (this will construct the leftsubtree) and elements which are right to i ( this will construct the rightSubtree).
- See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.
- See the picture and code.
Code:
Output:
Constructed Tree : 2 5 6 10 12 14 15