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

Objective: Given a 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 };

  • First element in DFS[] will be the root of the tree, here its 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 leftsubtree) and elements which are right to i ( this will construct the rightSubtree).
  • See this step above and recursively construct left subtree and link it root.left and recursively construct 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

Complete Code:

public class InorderDFStoTree {
int indexDFS = 0;
public Node makeBTree(int[] inorder, int[] DFS, int iStart, int iEnd) {
if (iStart > iEnd) {
return null;
}
int rootVal = DFS[indexDFS];
Node root = new Node(rootVal);
indexDFS++;
if (iStart == iEnd) {
return root;
}
int index = findIndex(inorder, rootVal, iStart, iEnd);
root.left = makeBTree(inorder, DFS, iStart, index 1);
root.right = makeBTree(inorder, DFS, index + 1, iEnd);
return root;
}
public int findIndex(int[] inorder, int value, int iStart, int iEnd) {
int x = 1;
for (int i = iStart; i <= iEnd; i++) {
if (value == inorder[i]) {
x = i;
}
}
return x;
}
public void printINORDER(Node root) {
if (root != null) {
printINORDER(root.left);
System.out.print(" " + root.data);
printINORDER(root.right);
}
}
public static void main(String args[]) {
int[] inOrder = { 8, 4, 2, 5, 1, 6, 3, 7, 9 };
int[] DFS = { 1, 2, 4, 8, 5, 3, 6, 7, 9 };
InorderDFStoTree i = new InorderDFStoTree();
Node x = i.makeBTree(inOrder, DFS, 0, inOrder.length 1);
System.out.println("inorder traversal of constructed tree : ");
i.printINORDER(x);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}


Output:

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