Construct Tree from given Inorder and Preorder traversals
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
A / \ / \ D B E F C
We recursively follow the above steps and get the following tree.
A / \ / \ B C / \ / / \ / D E F
Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick the next element in the next recursive call.
2) Create a new tree node tNode with the data as the picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as a left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as a right subtree of tNode.
6) return tNode.
Construct a Binary Tree from Postorder and Inorder
Given Postorder and Inorder traversals, construct the tree.
Examples:
Input: in[] = {2, 1, 3} post[] = {2, 3, 1} Output: Root of below tree 1 / \ 2 3 Input: in[] = {4, 8, 2, 5, 1, 6, 3, 7} post[] = {8, 4, 5, 2, 6, 7, 3, 1} Output: Root of below tree 1 / \ 2 3 / \ / \ 4 5 6 7 \ 8
1) We first find the last node in post[]. The last node is “1”, we know this value is root as the root always appears at the end of postorder traversal.
2) We search “1” in in[] to find the left and right subtrees of the root. Everything on the left of “1” in in[] is in the left subtree and everything on right is in the right subtree.
1 / \ [4, 8, 2, 5] [6, 3, 7]
3) We recur the above process for following two.
….b) Recur for in[] = {6, 3, 7} and post[] = {6, 7, 3}
…….Make the created tree as right child of root.
….a) Recur for in[] = {4, 8, 2, 5} and post[] = {8, 4, 5, 2}.
…….Make the created tree as left child of root.
Below is the implementation of the above idea. One important observation is, we recursively call for the right subtree before the left subtree as we decrease the index of the postorder index whenever we create a new node.
0 Comments