Given two arrays representing In-order and Preorder traversals of a binary tree, the task is to construct the tree and print "level-order" traversal.
Example 1: Construct Binary Tree from Preorder and In-order Traversal
Input : Inorder: 2,1,3, Pre-order: 1,2,3
Output : 1,2,3
1
/ \
2 3
Example 2: Construct Binary Tree from Preorder and In-order Traversal
Input : Inorder: 4,2,5,1,3,6, Pre-order: 1,2,4,5,3,6
Output : 1,2,3,4,5,6
1
/ \
2 3
/ \ /
4 5 6
Solutions
Method 1: Recursion
In a Preorder traversal, the left-most element is the root of the tree.
By searching "root" in the Inorder traversal, we can find out all elements on the left side of "root" is in the left subtree and elements on right in the right subtree.
We recursively follow the above steps and construct the final tree.
preOrderIndex -> 0
constructTree(int[] inOrder, int[] preOrder, int inStart, int inEnd)
if (inStart > inEnd)
return null
node -> new Node(preOrder[preOrderIndex++])
if (inStart == inEnd)
return node
divideIndex -> search(inOrder, inStart, inEnd, node.data)
node.left -> constructTree(inOrder, preOrder, inStart, divideIndex - 1)
node.right -> constructTree(inOrder, preOrder, divideIndex + 1, inEnd)
return node
search(int arr[], int start, int end, int value)
i
for (i = start; i <= end; i++)
if (arr[i] == value)
return i
return i
Complexity
The time complexity of this solution is O(n2) and space complexity is O(n) due to auxiliary stack.