algoadvance

Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

The problem requires us to construct a binary tree from its inorder and postorder traversal arrays.

Given two integer arrays inorder and postorder where:

• inorder is the inorder traversal of a binary tree.
• postorder is the postorder traversal of the same binary tree.

We need to construct and return the binary tree.

Constraints

• The number of nodes in the tree is in the range [0, 3000].
• -3000 <= Node.val <= 3000.

Clarifying Questions

1. Are there any duplicates in the tree nodes’ values?
   • No, all the values in the tree nodes are unique.
2. How should the constructed binary tree be returned?
   • The constructed tree should be returned as a root node of the TreeNode class.
3. What if the given arrays are empty?
   • If the arrays are empty, the function should return null.

Definition of TreeNode

Assuming the given structure for a 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;
    }
}

Strategy

1. Identify Root:
   • The last element of the postorder traversal is always the root of the binary tree.
2. Split Inorder Array:
   • Find the root in the inorder array. Elements to the left belong to the left subtree, and elements to the right belong to the right subtree.
3. Recursive Construction:
   • Recursively construct the left and right subtrees using slices of the inorder and postorder arrays.
4. Base Cases:
   • When the inorder or postorder arrays are empty, return null.

Code

Here is the Java code to construct the binary tree:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    private Map<Integer, Integer> inorderMap;
    private int postIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Initialize the postIndex to the last index in postorder array
        postIndex = postorder.length - 1;
        
        // Create a hashmap to store the value-to-index mappings for inorder traversal
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        
        return helper(0, inorder.length - 1, postorder);
    }

    private TreeNode helper(int inLeft, int inRight, int[] postorder) {
        // Base case: if there are no elements to construct the subtree
        if (inLeft > inRight) {
            return null;
        }

        // Select the postIndex element as root and decrement it
        int rootVal = postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);

        // Root splits inorder list into left and right subtrees
        int index = inorderMap.get(rootVal);

        // Build right subtree
        root.right = helper(index + 1, inRight, postorder);
        // Build left subtree
        root.left = helper(inLeft, index - 1, postorder);

        return root;
    }
}

Time Complexity

• Time Complexity: (O(n))
  • Each node is processed once.
  • HashMap operations (get/put) for each node are (O(1)).
• Space Complexity: (O(n))
  • The space complexity is dominated by the HashMap storing inorder index, and the recursion stack for balanced trees which could be (O(\log n)) in best cases, (O(n)) in the worst case. The HashMap itself requires (O(n)) space.

This solution efficiently constructs the binary tree using the given inorder and postorder traversals.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?