Constructing Binary Tree from In-order and Pre-order traversal in Java

In this post we will create a binary tree from the given in-order and pre-order traversal. You can find the details on the question here leetcode #105.

So, in a binary tree, we can do depth first traversal in three ways: 

In-order traversal  (left -> root -> right) 
Pre-order traversal  (root -> left -> right) 
Post-order traversal  (left -> right -> root) 

Refer Binary Tree - Traversal to understand on how to traverse using the above three ways.

Problem Statement

The problem states to construct the binary tree with the given pre-order traversal and in-order traversal. 

Inputs:
    pre-order    : [4, 2, 1, 3, 7, 6, 9]
    in-order      : [1, 2, 3, 4, 6, 7, 9]

Output:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Algorithm/Logic

Using the pre-order traversal, we can deduce that the first node in the pre-order array will be the root of the binary tree, we are going to construct. Further, now we will look in the in-order traversal for the root and whatever comes on the left side of the root in the in-order traversal will be the nodes present on the left side of the root node and whatever comes on the right side of the root in the in-order traversal will be on the right side of the root node.

From the first node in the pre-order traversal, we know that 4 is the root node of our binary tree. We will find the root node in in-order and divide the left nodes and right nodes.

     4
   /   \
1,2,3  6,7,9

Now, for the second round of recursion, we will take the left node list and perform the same approach as applied to find the first level of the binary tree. From the left node list (1, 2, 3), the root node will be 2 which is the next node after 4 in the pre-order traversal. Now, in the in-order traversal, nodes to the left of the new root node 2 is 1 and to the right of root node 2 is 3. So, we have the left nodes set for our binary tree. 

     4
   /   \
  2   6,7,9
 / \  
1   3 

Using the same approach, we can construct the rights nodes of our binary tree and can construct the entire binary tree. 

Code-snippet

Lets look how to create a Node of the binary tree:

public class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private String value;
    private int intValue;
    public TreeNode(String value){ this.value = value; }
    public TreeNode(int value){ this.intValue = value; }
    public TreeNode(TreeNode left, TreeNode right, String value){
        this.left = left;
        this.right = right;
        this.value = value;
    }
    public TreeNode(TreeNode left, TreeNode right, int value){
        this.left = left;
        this.right = right;
        this.intValue = value;
    }
    public TreeNode getLeft() { return left; }
    public void setLeft(TreeNode left) { this.left = left; }
    public TreeNode getRight() { return right; }
    public void setRight(TreeNode right) { this.right = right; }
    public String getValue() { return value; }
    public void setValue(String value) { this.value = value; }
    public int getIntValue() { return intValue; }
    public void setIntValue(int value) { this.intValue = value; }
}

With this, we will need a utility to find the root node in the in-order traversal in the given index range.

private int getNodeIndexInIn(int node, int[] inOrder, int start, int end){
    int index = 0;
    for(int i=start; i<=end; i++){
        if(node==inOrder[i]){
            index = i;
            return index;
        }
    }
    return index;
}

Now we will use recursion to create my left sub tree and then my right sub tree. To keep track on the node which will be our root for sub-trees, we will keep a global index variable.

//This will be used for get the root index in preOrder
private static int preRootIndex = 0;

public TreeNode constructBTree(String side, int inStart, int inEnd, int[] in, int[] pre){
    //1st Exit Criteria: Return null, when the indexes are crossing each other, means no value can be found in the array
    if(inStart > inEnd){
        return null;
    }
    int root = pre[preRootIndex++];
    TreeNode rootNode = new TreeNode(root);
    
    //Second exit criteria: When the node is a leaf node, means no left or right node exists, then return the node
    if (inStart == inEnd) {
        return rootNode;
    }
    //Find the rootIndex in Inorder array
    int rootIndexInInorder = getNodeIndexInIn(root, in, inStart, inEnd);

    rootNode.setLeft(constructBTree("left", inStart, rootIndexInInorder - 1, in, pre));
    rootNode.setRight(constructBTree("right", rootIndexInInorder + 1, inEnd, in, pre));

    return rootNode;
} 

NOTE: Always be extra careful for the exit criteria when you write programs using recursion. These exit points are the key in stopping the recursion. Else you will get StackOverflow error.

The code for the above program can be found here. Github Link

For any suggestion or modification, please comment down below.