Construct Binary Tree from Inorder and Postorder

Dec 18, 2024 • 5 mins read

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

The problem "Construct Binary Tree from Inorder and Postorder Traversal" is a fascinating task that involves reconstructing a binary tree using two types of tree traversals. This problem is part of LeetCode's catalog and is essential for understanding tree data structures and recursive problem-solving methods.

Problem Statement

Given two integer arrays, inorder and postorder, where inorder is the inorder traversal and postorder is the postorder traversal of a binary tree, your task is to reconstruct the binary tree and return its root.

inorder: The sequence of nodes visited in the left-root-right order.
postorder: The sequence of nodes visited in the left-right-root order.

Understanding the Problem

To solve this problem, we need a clear understanding of how the inorder and postorder traversals represent a binary tree.

Here is a brief explanation of both traversal types:

Inorder Traversal (L-R-N): This traversal visits the left subtree first, then the root node, and finally the right subtree.
Postorder Traversal (L-N-R): This traversal visits the left subtree, then the right subtree, and the root node at last.

With these definitions, the task is to utilize the given traversals to accurately rebuild the tree structure.

Key DSA Concepts and Theory

Binary Tree

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

Tree Traversals

Tree traversals are systematic ways of visiting all the nodes in the tree, and they are divided mainly into depth-first (Inorder, Preorder, Postorder) and breadth-first traversal (Level order).

Recursive Tree Construction

Trees can be constructed using recursion, a method where the solution to a problem depends on solutions to smaller instances of the same problem. Recursive construction makes use of dividing the tree problem into smaller subproblems, involving left and right subtrees.

Solution Approach

The main challenge is identifying root nodes from the traversals and partitioning the problem into smaller subproblems, i.e., constructing left and right subtrees recursively. We use the properties of postorder and inorder traversals for this.

Step-by-Step Approach

Identify the Root: In postorder traversal, the last element represents the root of the tree.
Divide the Tree: Using the root, divide the inorder traversal into left and right subtrees.
Recursive Construction: Recursively build the left and right subtrees using slices of the inorder and postorder lists.
Return the Built Tree: Assemble these subcomponents into the final tree structure.

C++ Code Implementation

#include <vector>
#include <unordered_map>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
        std::unordered_map<int, int> inorder_map;
        for(int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i;
        }
        return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorder_map);
    }

    TreeNode* buildTreeHelper(const std::vector<int>& inorder, int inStart, int inEnd,
                              const std::vector<int>& postorder, int postStart, int postEnd,
                              const std::unordered_map<int, int>& inorder_map) {
        if (postStart > postEnd || inStart > inEnd) return nullptr;

        int rootVal = postorder[postEnd];
        TreeNode* root = new TreeNode(rootVal);

        int inRootIndex = inorder_map.at(rootVal);
        int leftTreeSize = inRootIndex - inStart;

        root->left = buildTreeHelper(inorder, inStart, inRootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1, inorder_map);
        root->right = buildTreeHelper(inorder, inRootIndex + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1, inorder_map);

        return root;
    }
};

Java Code Implementation

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inorderMap);
    }

    private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd,
                                     int[] postorder, int postStart, int postEnd,
                                     Map<Integer, Integer> inorderMap) {
        if (postStart > postEnd || inStart > inEnd) return null;

        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        int inRootIndex = inorderMap.get(rootVal);
        int leftTreeSize = inRootIndex - inStart;

        root.left = buildTreeHelper(inorder, inStart, inRootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1, inorderMap);
        root.right = buildTreeHelper(inorder, inRootIndex + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1, inorderMap);

        return root;
    }
}

Time and Space Complexity Analysis

Time Complexity: The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because each node is processed once.
Space Complexity: The space complexity is O(n) due to the storage requirement for the map and the recursive stack (in the worst case, the depth of recursion can be the height of the tree, particularly in skewed trees).

Common Mistakes to Avoid

Incorrect Indexing: Carefully manage the indices when slicing arrays during recursion.
Root Identification: Ensure that root selection adheres to the postorder specification.
Recursive Base Cases: Properly handle the base cases for tree construction to avoid infinite recursion or null pointer issues.

Additional Resources and References

This article should provide a comprehensive insight into solving the given LeetCode problem using recursion and tree traversal properties. Happy Coding!