105. Construct Binary Tree from Preorder and Inorder Traversal

Intuition

Preorder and inorder traversals provide sufficient information to uniquely determine a binary tree. The first element in the preorder traversal is the root of the tree. In the inorder traversal, elements to the left of the root belong to the left subtree, and elements to the right belong to the right subtree. Using this information, we can recursively construct the binary tree.

Approach

1. Initialization: - Use two indices, p for the preorder array and i for the inorder array. - Initialize these indices to zero.
2. Recursive Tree Construction: - Define a helper function build(stop) that builds the tree up to a given stop value from the inorder array. - In the helper function: - If the current inorder value matches the stop value, return None. - Create a new TreeNode with the current value from preorder and increment the preorder index (p). - Recursively build the left subtree using the current root value as the new stop value. - Increment the inorder index (i). - Recursively build the right subtree using the initial stop value. - Return the root node.
3. Main Function: - Call the build function with the initial stop value None to construct the entire tree.

Complexity

Time Complexity:

O(N) where N is the number of nodes in the tree. Each node is visited once during the traversal.

Space Complexity:

O(N) for the recursion stack in the worst case of a completely unbalanced tree.

Code

C++

class Solution {
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        int p = 0, i = 0;
        return build(preorder, inorder, p, i, INT_MAX);
    }
private:
    TreeNode* build(vector& preorder, vector& inorder, int& p, int& i, int stop) {
        if (i < inorder.size() && inorder[i] != stop) {
            TreeNode* root = new TreeNode(preorder[p++]);
            root->left = build(preorder, inorder, p, i, root->val);
            i++;
            root->right = build(preorder, inorder, p, i, stop);
            return root;
        }
        return nullptr;
    }
};

Python

class Solution:
    def __init__(self):
        self.p = 0
        self.i = 0

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def build(stop):
            if self.i < len(inorder) and inorder[self.i] != stop:
                root = TreeNode(preorder[self.p])
                self.p += 1
                root.left = build(root.val)
                self.i += 1
                root.right = build(stop)
                return root
            return None

        return build(None)

Java

class Solution {
    private int p = 0;
    private int i = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MAX_VALUE);
    }
    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        if (i < inorder.length && inorder[i] != stop) {
            TreeNode root = new TreeNode(preorder[p++]);
            root.left = build(preorder, inorder, root.val);
            i++;
            root.right = build(preorder, inorder, stop);
            return root;
        }
        return null;
    }
}

JavaScript

var buildTree = function (preorder, inorder) 
{
    p = i = 0
    build = function (stop) 
    {
        if (inorder[i] != stop) {
            var root = new TreeNode(preorder[p++])
            root.left = build(root.val)
            i++
            root.right = build(stop)
            return root
        }
        return null
    }
    return build()
};