Java: Construct Binary Tree from Preorder and Inorder Traversal

Thought Process

The first element in the preorder array is always the root of the tree. We find the index of this root in the inorder array to determine the left and right subtrees. To build the left subtree, we recursively use the elements before the root in the inorder array. For the right subtree, we use the elements after the root. This ensures that the tree is constructed correctly. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class TreeNode{

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
class Solution {
    int idx = 0;

    int srchInOrder(int[] inOrder, int val){

        for(int i=0;i<inOrder.length;i++){
            if(inOrder[i]==val)
                return i;
        }
        return -1;
    }
    TreeNode makeTree(int[] preOrder, int[] inOrder, int start ,int end){

        if(start>end)
            return null;

        int root = preOrder[idx];
        int positionOfRoot = srchInOrder(inOrder,root);
        idx++;

        TreeNode rootNode = new TreeNode(root);

        if(start==end)
            return rootNode;

        rootNode.left = makeTree(preOrder,inOrder,start,positionOfRoot-1);
        rootNode.right = makeTree(preOrder,inOrder,positionOfRoot+1,end);
        
        return rootNode;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        int start = 0;
        int end = inorder.length-1;

        TreeNode root = makeTree(preorder,inorder, start, end);
        return root;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(n)

The space used by the recursion stack depends on the height of the tree. In the worst case, the space complexity is O(n).

Code copied!