Construct Binary Tree from Inorder and Postorder Traversal

class Solution {
    int current_post_idx;
    vector<int> postorder_seq;
    vector<int> inorder_seq;
    unordered_map<int, int> val_to_index_map;

public:
    TreeNode* construct_subtree(int in_left, int in_right) {
        if (in_left > in_right) return NULL;
        int root_value = postorder_seq[current_post_idx];
        TreeNode* root_node = new TreeNode(root_value);
        int split_index = val_to_index_map[root_value];
        current_post_idx--;
        root_node->right = construct_subtree(split_index + 1, in_right);
        root_node->left = construct_subtree(in_left, split_index - 1);
        return root_node;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->postorder_seq = postorder;
        this->inorder_seq = inorder;
        current_post_idx = postorder.size() - 1;
        int index_counter = 0;
        for (int value : inorder) val_to_index_map[value] = index_counter++;
        return construct_subtree(0, inorder.size() - 1);
    }
};

In the provided C++ solution, the goal is to reconstruct a binary tree from given inorder and postorder traversal sequences. Here’s a breakdown of how this solution efficiently accomplishes the task:

• Data Structures Used:

  • An integer (current_post_idx) to track the current index in the postorder sequence.
  • Two vectors (postorder_seq and inorder_seq) to store the postorder and inorder sequences.
  • An unordered map (val_to_index_map) to map each value in the inorder sequence to its index, facilitating quick lookup.

• Helper Function - construct_subtree:

  • This function is crucial for recursively constructing the binary tree. It takes two indices, in_left and in_right, defining the current segment of the inorder sequence being processed.
  • Base Case: If in_left is greater than in_right, it returns NULL, indicating no subtree exists for this segment.
  • A root value is selected from postorder_seq using current_post_idx and a new tree node is created with this value.
  • The index of this root value in the inorder sequence is found using val_to_index_map.
  • Recursively constructs the right subtree from the segment after the root’s index and the left subtree from the segment before the root’s index.
  • The current_post_idx is decremented after selecting the root value to move backwards through the postorder sequence.

• Function - buildTree:

  • Initializes the member variables with the provided inorder and postorder vectors.
  • Sets up the val_to_index_map with values and their corresponding indices from the inorder sequence.
  • Invokes construct_subtree with the entire range of the inorder sequence to construct and return the root of the binary tree.

The approach is effective for reconstructing the binary tree as it efficiently leverages the unordered map for quick index lookups and recursively divides the problem into constructing subtrees. This ensures that each element from the postorder sequence is used exactly once as the root of a subtree, adhering to the nature of postorder traversal. This solution is well-suited for problems requiring tree reconstruction from traversal outputs, ensuring a time complexity approximately proportional to the number of nodes, given the unordered map operations average constant time complexity.

class TreeBuilder {
    private int rootIndex;
    private int[] postorderSeq;
    private int[] inorderSeq;
    private HashMap<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildHelper(int leftLimit, int rightLimit) {
        if (leftLimit > rightLimit) {
            return null;
        }

        int rootValue = postorderSeq[rootIndex];
        TreeNode node = new TreeNode(rootValue);
        int pivot = indexMap.get(rootValue);

        rootIndex--;
        node.right = buildHelper(pivot + 1, rightLimit);
        node.left = buildHelper(leftLimit, pivot - 1);
        return node;
    }

    public TreeNode constructTree(int[] inorder, int[] postorder) {
        this.postorderSeq = postorder;
        this.inorderSeq = inorder;
        rootIndex = postorder.length - 1;

        int index = 0;
        for (int value : inorder) {
            indexMap.put(value, index++);
        }

        return buildHelper(0, inorder.length - 1);
    }
}

The Java solution provided constructs a binary tree from given inorder and postorder traversal arrays. Follow these steps to understand the code execution:

1. Initialize the TreeBuilder class which includes the necessary variables such as rootIndex, postorderSeq, inorderSeq, and indexMap for storing the traversal sequences and mapping the indices of inorder values.

2. The constructTree method sets the sequences of postorder and inorder traversals. It initializes rootIndex to point to the last element of the postorder array (which is the root of the tree). Populate the indexMap with elements from the inorder array, where the key is the value of the node, and the value is its index in the inorder array.

3. Execute buildHelper recursively to construct the binary tree. It accepts two parameters: leftLimit and rightLimit, which are initially set to the start and end of the inorder sequence, respectively. This method:

   • Checks if leftLimit exceeds rightLimit, in which case the method returns null indicating no subtree can be formed from this segment of the array.
   • Retrieves and removes the root node's value from postorderSeq using rootIndex and decreases rootIndex.
   • Identifies the pivot index of the current root in the inorder sequence using indexMap.
   • Recursively applies itself to construct the right and left subtrees. The right subtree is built first due to the nature of postorder traversal (left, right, root), and then the method progresses to constructing the left subtree.

4. The TreeNode class, utilized within this construction, must be defined outside of this snippet with at least the parameters int val; TreeNode left; TreeNode right;.

This code efficiently reconstructs the binary tree by leveraging the properties of binary tree traversals, notably using hashmap for indexing and recursive subtree construction. Thus, the overall time complexity relates closely to O(n) due to the single pass approach in mapping and constructing the tree.

struct TreeNode* constructTree(int* InOrd, int InSize, int* PostOrd, int PostSize) {
    if (InSize == 0) {
        return NULL;
    }
    int index;
    for (index = 0; index < InSize; index++) {
        if (InOrd[index] == PostOrd[PostSize - 1]) {
            break;
        }
    }
    struct TreeNode* rootNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    rootNode->val = PostOrd[PostSize - 1];
    rootNode->left = constructTree(InOrd, index, PostOrd, index);
    rootNode->right = constructTree(InOrd + index + 1, InSize - index - 1, PostOrd + index, PostSize - index - 1);
    return rootNode;
}

This solution demonstrates how to construct a binary tree from its inorder and postorder traversal arrays in C. Follow these steps to understand the implementation:

1. Check if the InSize (size of the inorder array) is zero. If it is, return NULL as it indicates that the tree or subtree has no elements.

2. Initialize a local variable index to find the root node in the inorder array. This root is identified as the last element in the postorder array PostOrd[PostSize - 1].

3. Iterate through the inorder array using a loop, comparing each element with the root value from the postorder array until it is found. Store this location in index.

4. Allocate memory for a new TreeNode which becomes the root node of the tree or subtree. Set the value of this node to PostOrd[PostSize - 1] (the root).

5. Recursively construct the left subtree using the first segment of the inorder and postorder arrays up to the index.

6. Similarly, construct the right subtree by invoking the function with the remaining elements of the inorder and postorder arrays, after excluding the elements used for the left subtree and the root.

7. Finally, return the rootNode which points to the constructed subtree or the complete tree based on the input arrays.

• This approach efficiently slices the problem into smaller subproblems, handling each subtree through recursive calls, and continuously building up the entire structure of the binary tree.

var constructTree = function(inorder, postorder) {
    var indexMap = {};
    var currentIndex = postorder.length - 1;
    var build = function(left, right) {
        if (left > right) return null;
        var rootValue = postorder[currentIndex];
        var rootNode = new TreeNode(rootValue);
        var i = indexMap[rootValue];
        currentIndex--;
        rootNode.right = build(i + 1, right);
        rootNode.left = build(left, i - 1);
        return rootNode;
    };
    for (var i = 0; i < inorder.length; i++) indexMap[inorder[i]] = i;
    return build(0, inorder.length - 1);
};

This JavaScript function constructs a binary tree using the given inorder and postorder traversal arrays. It utilizes the properties of these traversal methods to systematically rebuild the original tree. Here is a breakdown of how this implementation works:

1. An indexMap object is created to store the indices of elements in the inorder array, which helps in locating the roots quickly during tree construction.
2. currentIndex keeps track of the current index in the postorder array, starting from the last element, which is the root of the tree.
3. The build function is defined to construct the tree recursively. It accepts left and right parameters that delineate the current sub-array of the inorder array that the function is considering.
   • If left is greater than right, it indicates that there are no elements to construct the tree in this range, and hence returns null.
   • It retrieves the value of the current root from postorder using currentIndex and decrements currentIndex.
   • Using the value retrieved, it locates the index of this root in inorder through indexMap.
   • Recursively, it assigns the right child of the tree by considering the sub-array after this root index and the left child by considering the sub-array before this root index in inorder.
   • The function returns the constructed rootNode.
4. The indices of elements in inorder are initially stored in indexMap.
5. The build function is first called with the full range of the inorder array to commence the tree construction process.

By the end of the function execution, a binary tree based on the provided traversal arrays is constructed and returned.

class Solution:
    def constructBinaryTree(self, in_order: List[int], post_order: List[int]) -> TreeNode:
        def construct(in_start: int, in_end: int) -> TreeNode:
            if in_start > in_end:
                return None
            
            # Select the last element from postorder as root
            root_value = post_order.pop()
            new_root = TreeNode(root_value)
            
            # get the index of root in inorder list
            root_index = in_order_map[root_value]

            # Recursively construct right and then left subtree
            new_root.right = construct(root_index + 1, in_end)
            new_root.left = construct(in_start, root_index - 1)
            return new_root

        # Map to store the index of elements of inorder list
        in_order_map = {value: index for index, value in enumerate(in_order)}
        return construct(0, len(in_order) - 1)

To construct a binary tree from inorder and postorder traversal arrays using Python, follow these steps:

1. Start by creating a helper function, construct, that takes parameters in_start and in_end. These parameters define the current segment of the inorder array that needs to be processed.

   1. Check the base condition where in_start is greater than in_end. If true, return None, indicating no subtree can be formed from this segment.
   2. Retrieve and remove the last element from the post_order list. This element represents the root of the current subtree.
   3. Create a new tree node, new_root, with the retrieved root value.

2. Retrieve the index of the current root value in the inorder traversal using a precomputed map, in_order_map.

3. Recursively build the right subtree by calling the construct function with parameters (root_index + 1, in_end).

   1. Recursively build the left subtree by calling the construct function with parameters (in_start, root_index - 1).
   2. Return the new_root node. This node now points to a subtree with its correct left and right children constructed.

4. Before calling the helper function for the first time, preemptively build a map, in_order_map, where keys are elements from in_order list and values are their corresponding indexes. This map provides constant time complexity access to any element’s index in the inorder sequence to optimize the construction process.

5. Finally, call the construct function with parameters 0 and len(in_order) - 1 to initiate the construction of the entire binary tree and return the result.

The process effectively breaks down the problem into smaller subproblems by determining a root from the postorder array and then locating this root in the inorder array to decide the boundaries of left and right subtrees. This approach efficiently constructs a binary tree from the given traversals by utilizing recursive tree construction and hashmap lookups.