Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given the preorder and inorder traversal of a binary tree

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

The solution approach for this problem is same as construct-binary-tree-from-inorder-and-postorder-traversal

As discussed above the preorder traversal follows Root->Left->Right order, that makes it very convenient to construct the tree from its root.

Let’s do it. The first element in the preorder list is a root. This root splits inorder list into left and right subtrees. Now one have to pop up the root from preorder list since it’s already used as a tree node and then repeat the step above for the left and right subtrees.

class Solution {
    
    private int root_index = 0;
    private int[] preorder = null;
    private int[] inorder = null;
    private Map<Integer, Integer> inorderIndexMap = new HashMap<>();
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int n = inorder.length;
        for(int i = 0 ; i < n ; i++){
            inorderIndexMap.put(inorder[i], i);
        }
        return buildTree(0, n-1);
    }
    
    private TreeNode buildTree(int l, int r){
        if( l > r){
            return null;
        }
        int root_val = preorder[root_index++];
        TreeNode root = new TreeNode(root_val);
        int inorderIndexOfRoot = inorderIndexMap.get(root_val);
        root.left = buildTree(l, inorderIndexOfRoot-1);
        root.right = buildTree(inorderIndexOfRoot+1, r);
        return root;
    }
}

Categories: Binary Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s