Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Construct a Binary Tree from Given Inorder and Depth-First-Search.

Objec­tive: - Given a inorder and pre­order tra­ver­sal, con­struct a binary tree from that.

Input: Inorder tra­ver­sal 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 };

  • First ele­ment in DFS[] will be the root of the tree, here its 1.
  • Now the search ele­ment 1 in inorder[], say you find it at posi­tion i, once you find it, make note of ele­ments which are left to i (this will con­struct the left­sub­tree) and ele­ments which are right to i ( this will con­struct the rightSubtree).
  • See this step above and recur­sively con­struct left sub­tree and link it root.left and recur­sively con­struct right sub­tree and link it root.right.
  • See the pic­ture and code.
Construct-a-Binary-Tree-from-Given-Inorder-and-Depth-First-Search

Construct-a-Binary-Tree-from-Given-Inorder-and-Depth-First-Search

Com­plete Code:


Out­put:

inorder traversal of constructed tree : 
  8  4  2  5  1  6  3  7  9

You may also like...