LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal Solution

Master LeetCode problem 106 (Construct Binary Tree from Inorder and Postorder Traversal), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

106. Construct Binary Tree from Inorder and Postorder Traversal

Medium

Array Hash Table Divide and Conquer Tree Binary Tree

Problem Explanation

Explanation

To construct the binary tree from the given inorder and postorder traversal arrays, we can use a recursive approach. The idea is to start from the last element of the postorder array which will be the root of the binary tree. Then, we can find the index of this root element in the inorder array. The elements to the left of this index in the inorder array will form the left subtree, and the elements to the right will form the right subtree.

We can recursively build the left and right subtrees by passing the appropriate slices of the inorder and postorder arrays to the recursive calls.

Algorithm

Create a helper function that takes the inorder and postorder arrays along with the indices indicating the current range of elements.
If the range is empty, return null to indicate that there are no more elements to process.
Get the root value from the last element of the postorder array.
Find the index of the root value in the inorder array.
Create a new TreeNode with the root value.
Recursively call the helper function for the left subtree and right subtree with the updated ranges.
Update the left and right child of the current node with the results of the recursive calls.
Return the current node.

Time Complexity

The time complexity of this approach is O(N), where N is the number of nodes in the binary tree.

Space Complexity

The space complexity is O(N) for the recursive call stack.

Solution Code

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }
    
    private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        
        int rootIndex = inStart;
        while (inorder[rootIndex] != rootVal) {
            rootIndex++;
        }
        
        int leftSubtreeSize = rootIndex - inStart;
        
        root.left = buildTreeHelper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSubtreeSize - 1);
        root.right = buildTreeHelper(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSubtreeSize, postEnd - 1);
        
        return root;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 106 (Construct Binary Tree from Inorder and Postorder Traversal)?

This page provides optimized solutions for LeetCode problem 106 (Construct Binary Tree from Inorder and Postorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 106 (Construct Binary Tree from Inorder and Postorder Traversal)?

The time complexity for LeetCode 106 (Construct Binary Tree from Inorder and Postorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 106 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 106 in Java, C++, or Python.

Back to LeetCode Solutions