This post is completed by 1 user

  • 0
 Add to List
Hard

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

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

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 the 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.
Construct-a-Binary-Tree-from-Given-Inorder-and-Depth-First-Search
Construct-a-Binary-Tree-from-Given-Inorder-and-Depth-First-Search

Code:


Output:

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

Also Read: