|
This post is completed by 1 user
|
Add to List |
95. Construct a Binary Tree from Given Inorder and Depth-First-Search
Objective: - Generate a binary tree from given inorder and depth-first traversal arrays and perform inorder traversal to print the constructed tree.
Input: Inorder traversal and Depth-First-Search.
Approach:
int[] inOrder = { 8, 4, 2, 5, 1, 6, 3, 7, 9 };
int[] DFS = { 1, 2, 4, 8, 5, 3, 6, 7, 9 };
- The first element in DFS[] will be the root of the tree, here it's 1.
- Now search element 1 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 left subtree) and elements which are right to i ( this will construct the right subtree).
- See this step above and recursively construct the left subtree and link it root.left and recursively construct the right subtree and link it root.right.
- See the picture and code.
Output:
inorder traversal of constructed tree : 8 4 2 5 1 6 3 7 9