Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

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 tree

Construct and return the binary tree.

Examples

Input	Expected Output	Tree Structure
inorder: `[9,3,15,20,7]`, postorder: `[9,15,7,20,3]`	TreeNode(3)	`3` with left child `9` and right subtree `20` (children: `15`, `7`)
inorder: `[1]`, postorder: `[1]`	TreeNode(1)	Single node with value `1`
inorder: `[2,1,3]`, postorder: `[2,3,1]`	TreeNode(1)	`1` with left child `2` and right child `3`

Constraints

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder and postorder consist of unique values.
Each value of postorder also appears in inorder.
inorder is guaranteed to be the inorder traversal of the tree.
postorder is guaranteed to be the postorder traversal of the tree.

Real-World Applications

Complexity Comparison

Approach	Time	Space	Lookup	Best When
HashMap (Recommended)	O(n)	O(n)	O(1)	General case — optimal for all tree sizes
Index Tracking	O(n²)	O(h)	O(n)	Trees with minimal memory constraints (rare)

Which approach should you learn first?

Pick HashMap if you want the optimal solution — it’s the standard interview approach.
Pick Index Tracking if you want to understand the core recursion without HashMap overhead.

Optimal For Speed

HashMap

O(n) time · O(n) space

Memory Optimized

Index Tracking

O(n²) time · O(h) space

Approach 1: HashMap (Recommended)

★ Recommended

Use a HashMap to store each inorder value’s index. For each recursive step:

The last element in postorder is the current root.
Find the root’s position in inorder using the HashMap (O(1) lookup).
Count how many nodes are in the left subtree.
Recursively build the left and right subtrees using appropriate ranges.

⏱ Time O(n) Single pass with O(1) lookups 💾 Space O(n) HashMap + recursion stack

Step-by-step Example

Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]

Step	Postorder Range	Postorder[end]	Inorder Position	Left Subtree	Right Subtree
1	[9,15,7,20,3]	3 (root)	index 1	[9] at left	[15,20,7] at right
2	Left: [9]	9	index 0	(none)	(none) → return 9
3	Right: [9,15,7,20]	20 (root)	index 3	[15]	[7]
4	Left: [15]	15	index 2	(none)	(none) → return 15
5	Right: [7]	7	index 4	(none)	(none) → return 7

Result Tree:

Step 1 of 4 Target: HashMap

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function buildTreeHashMap(inorder, postorder):
    inorder_map = {}
    for i, val in enumerate(inorder):
        inorder_map[val] = i

    function build(post_start, post_end, in_start, in_end):
        if post_start > post_end or in_start > in_end:
            return null

        root_val = postorder[post_end]
        root = TreeNode(root_val)
        root_idx = inorder_map[root_val]
        left_size = root_idx - in_start

        root.left = build(post_start, post_start + left_size - 1, in_start, root_idx - 1)
        root.right = build(post_start + left_size, post_end - 1, root_idx + 1, in_end)
        return root

    return build(0, len(postorder) - 1, 0, len(inorder) - 1)

Solution Code

from typing import Optional, List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    """
    Construct binary tree from inorder and postorder traversal using HashMap.

    Key insight:
    - Postorder: left subtree, right subtree, root (last element is always root)
    - Inorder: left subtree, root, right subtree

    Use a HashMap to quickly find the root's position in inorder,
    then recursively build left and right subtrees.

    Time Complexity: O(n) where n is the number of nodes (HashMap lookup is O(1))
    Space Complexity: O(n) for the HashMap and recursion call stack
    """
    if not inorder or not postorder:
        return None

    # HashMap to store inorder values and their indices for O(1) lookup
    inorder_map = {val: idx for idx, val in enumerate(inorder)}

    def build(post_start: int, post_end: int, in_start: int, in_end: int) -> Optional[TreeNode]:
        """
        Recursively build tree from postorder and inorder ranges.

        Args:
            post_start, post_end: Range in postorder array
            in_start, in_end: Range in inorder array
        """
        if post_start > post_end or in_start > in_end:
            return None

        # Last element in postorder range is the root
        root_val = postorder[post_end]
        root = TreeNode(root_val)

        # Find root position in inorder
        root_idx = inorder_map[root_val]

        # Number of nodes in left subtree
        left_size = root_idx - in_start

        # Recursively build left subtree
        # Postorder: [left subtree], [right subtree], root
        # Inorder: [left subtree], root, [right subtree]
        root.left = build(
            post_start,           # Left subtree starts at beginning of postorder
            post_start + left_size - 1,  # Left subtree ends after left_size elements
            in_start,             # Left subtree starts at beginning of inorder
            root_idx - 1          # Left subtree ends before root
        )

        root.right = build(
            post_start + left_size,  # Right subtree starts after left subtree
            post_end - 1,         # Right subtree ends before root
            root_idx + 1,         # Right subtree starts after root
            in_end                # Right subtree ends at end of inorder
        )

        return root

    return build(0, len(postorder) - 1, 0, len(inorder) - 1)


# Test cases
if __name__ == "__main__":
    # Example 1: [3,9,20,null,null,15,7]
    #     3
    #    / \
    #   9  20
    #      / \
    #     15  7
    inorder1 = [9, 3, 15, 20, 7]
    postorder1 = [9, 15, 7, 20, 3]
    root1 = buildTree(inorder1, postorder1)

    def inorder_traversal(node):
        if not node:
            return []
        return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)

    def postorder_traversal(node):
        if not node:
            return []
        return postorder_traversal(node.left) + postorder_traversal(node.right) + [node.val]

    print(inorder_traversal(root1))    # Expected: [9, 3, 15, 20, 7]
    print(postorder_traversal(root1))  # Expected: [9, 15, 7, 20, 3]

    # Example 2: Single node
    inorder2 = [1]
    postorder2 = [1]
    root2 = buildTree(inorder2, postorder2)
    print(inorder_traversal(root2))    # Expected: [1]

    # Example 3: Left skewed tree
    inorder3 = [3, 2, 1]
    postorder3 = [3, 2, 1]
    root3 = buildTree(inorder3, postorder3)
    print(inorder_traversal(root3))    # Expected: [3, 2, 1]

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

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

class Solution {
public:
    unordered_map<int, int> inorder_map;

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        /**
         * Construct binary tree from inorder and postorder traversal using HashMap.
         *
         * Key insight:
         * - Postorder: left subtree, right subtree, root (last element is always root)
         * - Inorder: left subtree, root, right subtree
         *
         * Use a HashMap to quickly find the root's position in inorder,
         * then recursively build left and right subtrees.
         *
         * Time Complexity: O(n) where n is the number of nodes
         * Space Complexity: O(n) for HashMap and recursion call stack
         */

        if (inorder.empty() || postorder.empty()) {
            return nullptr;
        }

        // Build HashMap for O(1) inorder lookup
        for (int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i;
        }

        return build(postorder, 0, postorder.size() - 1, 0, inorder.size() - 1);
    }

private:
    TreeNode* build(vector<int>& postorder, int post_start, int post_end,
                    int in_start, int in_end) {
        /**
         * Recursively build tree from postorder and inorder ranges.
         *
         * Args:
         *     post_start, post_end: Range in postorder array
         *     in_start, in_end: Range in inorder array
         */

        if (post_start > post_end || in_start > in_end) {
            return nullptr;
        }

        // Last element in postorder range is the root
        int root_val = postorder[post_end];
        TreeNode* root = new TreeNode(root_val);

        // Find root position in inorder
        int root_idx = inorder_map[root_val];

        // Number of nodes in left subtree
        int left_size = root_idx - in_start;

        // Recursively build left subtree
        root->left = build(postorder, post_start, post_start + left_size - 1,
                          in_start, root_idx - 1);

        // Recursively build right subtree
        root->right = build(postorder, post_start + left_size, post_end - 1,
                           root_idx + 1, in_end);

        return root;
    }
};

// Helper function for inorder traversal
vector<int> inorder_traversal(TreeNode* node) {
    if (!node) return {};
    vector<int> result;
    inorder_traversal(node->left, result);
    result.push_back(node->val);
    inorder_traversal(node->right, result);
    return result;
}

void inorder_traversal(TreeNode* node, vector<int>& result) {
    if (!node) return;
    inorder_traversal(node->left, result);
    result.push_back(node->val);
    inorder_traversal(node->right, result);
}

// Helper function for postorder traversal
vector<int> postorder_traversal(TreeNode* node) {
    if (!node) return {};
    vector<int> result;
    postorder_traversal(node->left, result);
    postorder_traversal(node->right, result);
    result.push_back(node->val);
    return result;
}

void postorder_traversal(TreeNode* node, vector<int>& result) {
    if (!node) return;
    postorder_traversal(node->left, result);
    postorder_traversal(node->right, result);
    result.push_back(node->val);
}

int main() {
    Solution sol;

    // Example 1: [3,9,20,null,null,15,7]
    //     3
    //    / \
    //   9  20
    //      / \
    //     15  7
    vector<int> inorder1 = {9, 3, 15, 20, 7};
    vector<int> postorder1 = {9, 15, 7, 20, 3};
    TreeNode* root1 = sol.buildTree(inorder1, postorder1);

    vector<int> result1 = inorder_traversal(root1);
    cout << "Inorder: ";
    for (int val : result1) cout << val << " ";
    cout << "\n";  // Expected: 9 3 15 20 7

    vector<int> result1_post = postorder_traversal(root1);
    cout << "Postorder: ";
    for (int val : result1_post) cout << val << " ";
    cout << "\n";  // Expected: 9 15 7 20 3

    return 0;
}

import java.util.*;

public class construct_binary_tree_from_inorder_and_postorder_traversal_hash_map {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        private Map<Integer, Integer> inorder_map;

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            /**
             * Construct binary tree from inorder and postorder traversal using HashMap.
             *
             * Key insight:
             * - Postorder: left subtree, right subtree, root (last element is always root)
             * - Inorder: left subtree, root, right subtree
             *
             * Use a HashMap to quickly find the root's position in inorder,
             * then recursively build left and right subtrees.
             *
             * Time Complexity: O(n) where n is the number of nodes
             * Space Complexity: O(n) for HashMap and recursion call stack
             */

            if (inorder.length == 0 || postorder.length == 0) {
                return null;
            }

            // Build HashMap for O(1) inorder lookup
            inorder_map = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                inorder_map.put(inorder[i], i);
            }

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

        private TreeNode build(int[] postorder, int post_start, int post_end,
                              int in_start, int in_end) {
            /**
             * Recursively build tree from postorder and inorder ranges.
             *
             * Args:
             *     post_start, post_end: Range in postorder array
             *     in_start, in_end: Range in inorder array
             */

            if (post_start > post_end || in_start > in_end) {
                return null;
            }

            // Last element in postorder range is the root
            int root_val = postorder[post_end];
            TreeNode root = new TreeNode(root_val);

            // Find root position in inorder
            int root_idx = inorder_map.get(root_val);

            // Number of nodes in left subtree
            int left_size = root_idx - in_start;

            // Recursively build left subtree
            root.left = build(postorder, post_start, post_start + left_size - 1,
                             in_start, root_idx - 1);

            // Recursively build right subtree
            root.right = build(postorder, post_start + left_size, post_end - 1,
                              root_idx + 1, in_end);

            return root;
        }
    }

    // Helper function for inorder traversal
    static List<Integer> inorder_traversal(TreeNode node) {
        List<Integer> result = new ArrayList<>();
        inorder_helper(node, result);
        return result;
    }

    static void inorder_helper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder_helper(node.left, result);
        result.add(node.val);
        inorder_helper(node.right, result);
    }

    // Helper function for postorder traversal
    static List<Integer> postorder_traversal(TreeNode node) {
        List<Integer> result = new ArrayList<>();
        postorder_helper(node, result);
        return result;
    }

    static void postorder_helper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        postorder_helper(node.left, result);
        postorder_helper(node.right, result);
        result.add(node.val);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Example 1: [3,9,20,null,null,15,7]
        //     3
        //    / \
        //   9  20
        //      / \
        //     15  7
        int[] inorder1 = {9, 3, 15, 20, 7};
        int[] postorder1 = {9, 15, 7, 20, 3};
        TreeNode root1 = sol.buildTree(inorder1, postorder1);

        System.out.print("Inorder: ");
        System.out.println(inorder_traversal(root1));  // Expected: [9, 3, 15, 20, 7]

        System.out.print("Postorder: ");
        System.out.println(postorder_traversal(root1));  // Expected: [9, 15, 7, 20, 3]

        // Example 2: Single node
        int[] inorder2 = {1};
        int[] postorder2 = {1};
        TreeNode root2 = sol.buildTree(inorder2, postorder2);
        System.out.println("Single node inorder: " + inorder_traversal(root2));

        // Example 3: Left skewed tree
        int[] inorder3 = {3, 2, 1};
        int[] postorder3 = {3, 2, 1};
        TreeNode root3 = sol.buildTree(inorder3, postorder3);
        System.out.println("Left skewed inorder: " + inorder_traversal(root3));
    }
}

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Construct binary tree from inorder and postorder traversal using HashMap.
 *
 * Key insight:
 * - Postorder: left subtree, right subtree, root (last element is always root)
 * - Inorder: left subtree, root, right subtree
 *
 * Use a HashMap to quickly find the root's position in inorder,
 * then recursively build left and right subtrees.
 *
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(n) for HashMap and recursion call stack
 */
var buildTree = function (inorder, postorder) {
    if (inorder.length === 0 || postorder.length === 0) {
        return null;
    }

    // Build HashMap for O(1) inorder lookup
    const inorder_map = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorder_map.set(inorder[i], i);
    }

    const build = (post_start, post_end, in_start, in_end) => {
        /**
         * Recursively build tree from postorder and inorder ranges.
         *
         * @param {number} post_start, post_end - Range in postorder array
         * @param {number} in_start, in_end - Range in inorder array
         * @return {TreeNode}
         */

        if (post_start > post_end || in_start > in_end) {
            return null;
        }

        // Last element in postorder range is the root
        const root_val = postorder[post_end];
        const root = new TreeNode(root_val);

        // Find root position in inorder
        const root_idx = inorder_map.get(root_val);

        // Number of nodes in left subtree
        const left_size = root_idx - in_start;

        // Recursively build left subtree
        root.left = build(
            post_start,
            post_start + left_size - 1,
            in_start,
            root_idx - 1
        );

        // Recursively build right subtree
        root.right = build(
            post_start + left_size,
            post_end - 1,
            root_idx + 1,
            in_end
        );

        return root;
    };

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

// Helper function for inorder traversal
function inorder_traversal(node) {
    if (!node) return [];
    return [
        ...inorder_traversal(node.left),
        node.val,
        ...inorder_traversal(node.right),
    ];
}

// Helper function for postorder traversal
function postorder_traversal(node) {
    if (!node) return [];
    return [
        ...postorder_traversal(node.left),
        ...postorder_traversal(node.right),
        node.val,
    ];
}

// Test cases
if (require.main === module) {
    // Example 1: [3,9,20,null,null,15,7]
    //     3
    //    / \
    //   9  20
    //      / \
    //     15  7
    const inorder1 = [9, 3, 15, 20, 7];
    const postorder1 = [9, 15, 7, 20, 3];
    const root1 = buildTree(inorder1, postorder1);

    console.log("Inorder:", inorder_traversal(root1));   // Expected: [9, 3, 15, 20, 7]
    console.log("Postorder:", postorder_traversal(root1)); // Expected: [9, 15, 7, 20, 3]

    // Example 2: Single node
    const inorder2 = [1];
    const postorder2 = [1];
    const root2 = buildTree(inorder2, postorder2);
    console.log("Single node:", inorder_traversal(root2));

    // Example 3: Left skewed tree
    const inorder3 = [3, 2, 1];
    const postorder3 = [3, 2, 1];
    const root3 = buildTree(inorder3, postorder3);
    console.log("Left skewed:", inorder_traversal(root3));
}

module.exports = { buildTree, TreeNode };

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Construct binary tree from inorder and postorder traversal using HashMap.
 *
 * Key insight:
 * - Postorder: left subtree, right subtree, root (last element is always root)
 * - Inorder: left subtree, root, right subtree
 *
 * Use a HashMap to quickly find the root's position in inorder,
 * then recursively build left and right subtrees.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(n) for HashMap and recursion call stack
 */
pub fn build_tree(
    inorder: Vec<i32>,
    postorder: Vec<i32>,
) -> Option<Rc<RefCell<TreeNode>>> {
    if inorder.is_empty() || postorder.is_empty() {
        return None;
    }

    // Build HashMap for O(1) inorder lookup
    let inorder_map: HashMap<i32, usize> = inorder
        .iter()
        .enumerate()
        .map(|(i, &val)| (val, i))
        .collect();

    fn build(
        postorder: &[i32],
        post_start: usize,
        post_end: usize,
        in_start: usize,
        in_end: usize,
        inorder_map: &HashMap<i32, usize>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        /**
         * Recursively build tree from postorder and inorder ranges.
         *
         * Args:
         *     post_start, post_end: Range in postorder array
         *     in_start, in_end: Range in inorder array
         */

        if post_start > post_end || in_start > in_end {
            return None;
        }

        // Last element in postorder range is the root
        let root_val = postorder[post_end];
        let mut root = TreeNode::new(root_val);

        // Find root position in inorder
        let root_idx = inorder_map[&root_val];

        // Number of nodes in left subtree
        let left_size = root_idx - in_start;

        // Recursively build left subtree
        root.left = build(
            postorder,
            post_start,
            post_start + left_size - 1,
            in_start,
            root_idx - 1,
            inorder_map,
        );

        // Recursively build right subtree
        root.right = build(
            postorder,
            post_start + left_size,
            post_end - 1,
            root_idx + 1,
            in_end,
            inorder_map,
        );

        Some(Rc::new(RefCell::new(root)))
    }

    build(&postorder, 0, postorder.len() - 1, 0, inorder.len() - 1, &inorder_map)
}

// Helper function for inorder traversal
fn inorder_traversal(node: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    match node {
        None => vec![],
        Some(n) => {
            let n_ref = n.borrow();
            let mut result = inorder_traversal(n_ref.left.clone());
            result.push(n_ref.val);
            result.extend(inorder_traversal(n_ref.right.clone()));
            result
        }
    }
}

// Helper function for postorder traversal
fn postorder_traversal(node: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    match node {
        None => vec![],
        Some(n) => {
            let n_ref = n.borrow();
            let mut result = postorder_traversal(n_ref.left.clone());
            result.extend(postorder_traversal(n_ref.right.clone()));
            result.push(n_ref.val);
            result
        }
    }
}

fn main() {
    // Example 1: [3,9,20,null,null,15,7]
    //     3
    //    / \
    //   9  20
    //      / \
    //     15  7
    let inorder1 = vec![9, 3, 15, 20, 7];
    let postorder1 = vec![9, 15, 7, 20, 3];
    let root1 = build_tree(inorder1, postorder1);

    println!("Inorder: {:?}", inorder_traversal(root1.clone()));   // Expected: [9, 3, 15, 20, 7]
    println!("Postorder: {:?}", postorder_traversal(root1));      // Expected: [9, 15, 7, 20, 3]

    // Example 2: Single node
    let inorder2 = vec![1];
    let postorder2 = vec![1];
    let root2 = build_tree(inorder2, postorder2);
    println!("Single node: {:?}", inorder_traversal(root2));

    // Example 3: Left skewed tree
    let inorder3 = vec![3, 2, 1];
    let postorder3 = vec![3, 2, 1];
    let root3 = build_tree(inorder3, postorder3);
    println!("Left skewed: {:?}", inorder_traversal(root3));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example1() {
        let inorder = vec![9, 3, 15, 20, 7];
        let postorder = vec![9, 15, 7, 20, 3];
        let root = build_tree(inorder, postorder);
        assert_eq!(inorder_traversal(root), vec![9, 3, 15, 20, 7]);
    }

    #[test]
    fn test_single_node() {
        let inorder = vec![1];
        let postorder = vec![1];
        let root = build_tree(inorder, postorder);
        assert_eq!(inorder_traversal(root), vec![1]);
    }
}

package main

import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/*
buildTree constructs a binary tree from inorder and postorder traversal using HashMap.

Key insight:
- Postorder: left subtree, right subtree, root (last element is always root)
- Inorder: left subtree, root, right subtree

Use a HashMap to quickly find the root's position in inorder,
then recursively build left and right subtrees.

Time Complexity: O(n) where n is the number of nodes
Space Complexity: O(n) for HashMap and recursion call stack
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
  if len(inorder) == 0 || len(postorder) == 0 {
    return nil
  }

  // Build map for O(1) inorder lookup
  inorderMap := make(map[int]int)
  for i, val := range inorder {
    inorderMap[val] = i
  }

  var build func(postStart, postEnd, inStart, inEnd int) *TreeNode
  build = func(postStart, postEnd, inStart, inEnd int) *TreeNode {
    /*
    Recursively build tree from postorder and inorder ranges.

    Args:
        postStart, postEnd: Range in postorder array
        inStart, inEnd: Range in inorder array
    */

    if postStart > postEnd || inStart > inEnd {
      return nil
    }

    // Last element in postorder range is the root
    rootVal := postorder[postEnd]
    root := &TreeNode{Val: rootVal}

    // Find root position in inorder
    rootIdx := inorderMap[rootVal]

    // Number of nodes in left subtree
    leftSize := rootIdx - inStart

    // Recursively build left subtree
    root.Left = build(postStart, postStart+leftSize-1, inStart, rootIdx-1)

    // Recursively build right subtree
    root.Right = build(postStart+leftSize, postEnd-1, rootIdx+1, inEnd)

    return root
  }

  return build(0, len(postorder)-1, 0, len(inorder)-1)
}

// Helper function for inorder traversal
func inorderTraversal(node *TreeNode) []int {
  if node == nil {
    return []int{}
  }
  result := inorderTraversal(node.Left)
  result = append(result, node.Val)
  result = append(result, inorderTraversal(node.Right)...)
  return result
}

// Helper function for postorder traversal
func postorderTraversal(node *TreeNode) []int {
  if node == nil {
    return []int{}
  }
  result := postorderTraversal(node.Left)
  result = append(result, postorderTraversal(node.Right)...)
  result = append(result, node.Val)
  return result
}

func main() {
  // Example 1: [3,9,20,null,null,15,7]
  //     3
  //    / \
  //   9  20
  //      / \
  //     15  7
  inorder1 := []int{9, 3, 15, 20, 7}
  postorder1 := []int{9, 15, 7, 20, 3}
  root1 := buildTree(inorder1, postorder1)

  fmt.Println("Inorder:", inorderTraversal(root1))     // Expected: [9 3 15 20 7]
  fmt.Println("Postorder:", postorderTraversal(root1)) // Expected: [9 15 7 20 3]

  // Example 2: Single node
  inorder2 := []int{1}
  postorder2 := []int{1}
  root2 := buildTree(inorder2, postorder2)
  fmt.Println("Single node:", inorderTraversal(root2))

  // Example 3: Left skewed tree
  inorder3 := []int{3, 2, 1}
  postorder3 := []int{3, 2, 1}
  root3 := buildTree(inorder3, postorder3)
  fmt.Println("Left skewed:", inorderTraversal(root3))
}

Approach 2: Index Tracking

🎯 Interview Favourite

Instead of a HashMap, use an index pointer into the postorder array. Process the postorder sequence from right to left (backwards) and use indexOf() to find the root’s position in inorder each time.

The key insight is that traversing postorder backwards naturally aligns with the order in which we need to construct nodes (root first, then right, then left).

⏱ Time O(n²) Linear inorder search per node 💾 Space O(h) Recursion stack only

Step-by-step Example

Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]

Processing postorder from right to left:

Step	Postorder Pointer	Value	Inorder Search	Action
1	index 4	3	found at 1	Create root, split subtrees
2	index 3	20	found at 3	Create right subtree root
3	index 2	7	found at 4	Create right child of 20
4	index 1	15	found at 2	Create left child of 20
5	index 0	9	found at 0	Create left child of root

Pseudocode

function buildTreeIndexTracking(inorder, postorder):
    post_idx = len(postorder) - 1

    function build(in_start, in_end):
        if in_start > in_end or post_idx < 0:
            return null

        root_val = postorder[post_idx]
        post_idx--
        root = TreeNode(root_val)
        root_idx = inorder.indexOf(root_val)

        root.right = build(root_idx + 1, in_end)   // Right before left (postorder is reverse)
        root.left = build(in_start, root_idx - 1)
        return root

    return build(0, len(inorder) - 1)

Solution Code

from typing import Optional, List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    """
    Construct binary tree from inorder and postorder traversal using index tracking.

    Key insight:
    - Postorder: left subtree, right subtree, root (last element is always root)
    - Inorder: left subtree, root, right subtree
    - Use a pointer to track the current root in postorder (traverse from end to start)
    - Find root in inorder to split into left and right subtrees

    Time Complexity: O(n²) in worst case due to linear search for root in inorder
                      O(n) if inorder is indexed (see hash_map approach)
    Space Complexity: O(h) for recursion call stack where h is height
    """
    if not inorder or not postorder:
        return None

    # Use a list to hold the postorder index as a reference (non-local variable)
    post_idx = [len(postorder) - 1]

    def build(in_start: int, in_end: int) -> Optional[TreeNode]:
        """
        Recursively build tree by processing postorder from right to left.

        Args:
            in_start, in_end: Range in inorder array
        """
        if in_start > in_end or post_idx[0] < 0:
            return None

        # Current postorder element (processing from end to start)
        root_val = postorder[post_idx[0]]
        post_idx[0] -= 1

        root = TreeNode(root_val)

        # Find root position in inorder
        root_idx = inorder.index(root_val)

        # Build right subtree first (postorder: left, right, root)
        # Since we traverse postorder backwards, right comes before left
        root.right = build(root_idx + 1, in_end)

        # Build left subtree
        root.left = build(in_start, root_idx - 1)

        return root

    return build(0, len(inorder) - 1)


# Test cases
if __name__ == "__main__":
    # Example 1: [3,9,20,null,null,15,7]
    #     3
    #    / \
    #   9  20
    #      / \
    #     15  7
    inorder1 = [9, 3, 15, 20, 7]
    postorder1 = [9, 15, 7, 20, 3]
    root1 = buildTree(inorder1, postorder1)

    def inorder_traversal(node):
        if not node:
            return []
        return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)

    def postorder_traversal(node):
        if not node:
            return []
        return postorder_traversal(node.left) + postorder_traversal(node.right) + [node.val]

    print(inorder_traversal(root1))    # Expected: [9, 3, 15, 20, 7]
    print(postorder_traversal(root1))  # Expected: [9, 15, 7, 20, 3]

    # Example 2: Single node
    inorder2 = [1]
    postorder2 = [1]
    root2 = buildTree(inorder2, postorder2)
    print(inorder_traversal(root2))    # Expected: [1]

    # Example 3: Left skewed tree
    inorder3 = [3, 2, 1]
    postorder3 = [3, 2, 1]
    root3 = buildTree(inorder3, postorder3)
    print(inorder_traversal(root3))    # Expected: [3, 2, 1]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

class Solution {
public:
    int post_idx;

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        /**
         * Construct binary tree from inorder and postorder traversal using index tracking.
         *
         * Key insight:
         * - Postorder: left subtree, right subtree, root (last element is always root)
         * - Inorder: left subtree, root, right subtree
         * - Use a pointer to track the current root in postorder (traverse from end to start)
         * - Find root in inorder to split into left and right subtrees
         *
         * Time Complexity: O(n²) in worst case due to linear search for root in inorder
         * Space Complexity: O(h) for recursion call stack where h is height
         */

        if (inorder.empty() || postorder.empty()) {
            return nullptr;
        }

        post_idx = postorder.size() - 1;
        return build(postorder, inorder, 0, inorder.size() - 1);
    }

private:
    TreeNode* build(vector<int>& postorder, vector<int>& inorder,
                   int in_start, int in_end) {
        /**
         * Recursively build tree by processing postorder from right to left.
         *
         * Args:
         *     in_start, in_end: Range in inorder array
         */

        if (in_start > in_end || post_idx < 0) {
            return nullptr;
        }

        // Current postorder element (processing from end to start)
        int root_val = postorder[post_idx];
        post_idx--;

        TreeNode* root = new TreeNode(root_val);

        // Find root position in inorder
        int root_idx = find(inorder.begin() + in_start, inorder.begin() + in_end + 1, root_val)
                       - inorder.begin();

        // Build right subtree first (postorder: left, right, root)
        // Since we traverse postorder backwards, right comes before left
        root->right = build(postorder, inorder, root_idx + 1, in_end);

        // Build left subtree
        root->left = build(postorder, inorder, in_start, root_idx - 1);

        return root;
    }
};

// Helper function for inorder traversal
void inorder_traversal(TreeNode* node, vector<int>& result) {
    if (!node) return;
    inorder_traversal(node->left, result);
    result.push_back(node->val);
    inorder_traversal(node->right, result);
}

// Helper function for postorder traversal
void postorder_traversal(TreeNode* node, vector<int>& result) {
    if (!node) return;
    postorder_traversal(node->left, result);
    postorder_traversal(node->right, result);
    result.push_back(node->val);
}

int main() {
    Solution sol;

    // Example 1: [3,9,20,null,null,15,7]
    //     3
    //    / \
    //   9  20
    //      / \
    //     15  7
    vector<int> inorder1 = {9, 3, 15, 20, 7};
    vector<int> postorder1 = {9, 15, 7, 20, 3};
    TreeNode* root1 = sol.buildTree(inorder1, postorder1);

    vector<int> result1;
    inorder_traversal(root1, result1);
    cout << "Inorder: ";
    for (int val : result1) cout << val << " ";
    cout << "\n";  // Expected: 9 3 15 20 7

    vector<int> result1_post;
    postorder_traversal(root1, result1_post);
    cout << "Postorder: ";
    for (int val : result1_post) cout << val << " ";
    cout << "\n";  // Expected: 9 15 7 20 3

    return 0;
}

import java.util.*;

public class construct_binary_tree_from_inorder_and_postorder_traversal_index {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        private int post_idx;

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            /**
             * Construct binary tree from inorder and postorder traversal using index tracking.
             *
             * Key insight:
             * - Postorder: left subtree, right subtree, root (last element is always root)
             * - Inorder: left subtree, root, right subtree
             * - Use a pointer to track the current root in postorder (traverse from end to start)
             * - Find root in inorder to split into left and right subtrees
             *
             * Time Complexity: O(n²) in worst case due to linear search for root in inorder
             * Space Complexity: O(h) for recursion call stack where h is height
             */

            if (inorder.length == 0 || postorder.length == 0) {
                return null;
            }

            post_idx = postorder.length - 1;
            return build(postorder, inorder, 0, inorder.length - 1);
        }

        private TreeNode build(int[] postorder, int[] inorder, int in_start, int in_end) {
            /**
             * Recursively build tree by processing postorder from right to left.
             *
             * Args:
             *     in_start, in_end: Range in inorder array
             */

            if (in_start > in_end || post_idx < 0) {
                return null;
            }

            // Current postorder element (processing from end to start)
            int root_val = postorder[post_idx];
            post_idx--;

            TreeNode root = new TreeNode(root_val);

            // Find root position in inorder
            int root_idx = -1;
            for (int i = in_start; i <= in_end; i++) {
                if (inorder[i] == root_val) {
                    root_idx = i;
                    break;
                }
            }

            // Build right subtree first (postorder: left, right, root)
            // Since we traverse postorder backwards, right comes before left
            root.right = build(postorder, inorder, root_idx + 1, in_end);

            // Build left subtree
            root.left = build(postorder, inorder, in_start, root_idx - 1);

            return root;
        }
    }

    // Helper function for inorder traversal
    static List<Integer> inorder_traversal(TreeNode node) {
        List<Integer> result = new ArrayList<>();
        inorder_helper(node, result);
        return result;
    }

    static void inorder_helper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder_helper(node.left, result);
        result.add(node.val);
        inorder_helper(node.right, result);
    }

    // Helper function for postorder traversal
    static List<Integer> postorder_traversal(TreeNode node) {
        List<Integer> result = new ArrayList<>();
        postorder_helper(node, result);
        return result;
    }

    static void postorder_helper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        postorder_helper(node.left, result);
        postorder_helper(node.right, result);
        result.add(node.val);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Example 1: [3,9,20,null,null,15,7]
        //     3
        //    / \
        //   9  20
        //      / \
        //     15  7
        int[] inorder1 = {9, 3, 15, 20, 7};
        int[] postorder1 = {9, 15, 7, 20, 3};
        TreeNode root1 = sol.buildTree(inorder1, postorder1);

        System.out.print("Inorder: ");
        System.out.println(inorder_traversal(root1));  // Expected: [9, 3, 15, 20, 7]

        System.out.print("Postorder: ");
        System.out.println(postorder_traversal(root1));  // Expected: [9, 15, 7, 20, 3]

        // Example 2: Single node
        int[] inorder2 = {1};
        int[] postorder2 = {1};
        TreeNode root2 = sol.buildTree(inorder2, postorder2);
        System.out.println("Single node inorder: " + inorder_traversal(root2));

        // Example 3: Left skewed tree
        int[] inorder3 = {3, 2, 1};
        int[] postorder3 = {3, 2, 1};
        TreeNode root3 = sol.buildTree(inorder3, postorder3);
        System.out.println("Left skewed inorder: " + inorder_traversal(root3));
    }
}

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Construct binary tree from inorder and postorder traversal using index tracking.
 *
 * Key insight:
 * - Postorder: left subtree, right subtree, root (last element is always root)
 * - Inorder: left subtree, root, right subtree
 * - Use a pointer to track the current root in postorder (traverse from end to start)
 * - Find root in inorder to split into left and right subtrees
 *
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 *
 * Time Complexity: O(n²) in worst case due to linear search for root in inorder
 * Space Complexity: O(h) for recursion call stack where h is height
 */
var buildTree = function (inorder, postorder) {
    if (inorder.length === 0 || postorder.length === 0) {
        return null;
    }

    let post_idx = postorder.length - 1;

    const build = (in_start, in_end) => {
        /**
         * Recursively build tree by processing postorder from right to left.
         *
         * @param {number} in_start, in_end - Range in inorder array
         * @return {TreeNode}
         */

        if (in_start > in_end || post_idx < 0) {
            return null;
        }

        // Current postorder element (processing from end to start)
        const root_val = postorder[post_idx];
        post_idx--;

        const root = new TreeNode(root_val);

        // Find root position in inorder
        const root_idx = inorder.indexOf(root_val);

        // Build right subtree first (postorder: left, right, root)
        // Since we traverse postorder backwards, right comes before left
        root.right = build(root_idx + 1, in_end);

        // Build left subtree
        root.left = build(in_start, root_idx - 1);

        return root;
    };

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

// Helper function for inorder traversal
function inorder_traversal(node) {
    if (!node) return [];
    return [
        ...inorder_traversal(node.left),
        node.val,
        ...inorder_traversal(node.right),
    ];
}

// Helper function for postorder traversal
function postorder_traversal(node) {
    if (!node) return [];
    return [
        ...postorder_traversal(node.left),
        ...postorder_traversal(node.right),
        node.val,
    ];
}

// Test cases
if (require.main === module) {
    // Example 1: [3,9,20,null,null,15,7]
    //     3
    //    / \
    //   9  20
    //      / \
    //     15  7
    const inorder1 = [9, 3, 15, 20, 7];
    const postorder1 = [9, 15, 7, 20, 3];
    const root1 = buildTree(inorder1, postorder1);

    console.log("Inorder:", inorder_traversal(root1));   // Expected: [9, 3, 15, 20, 7]
    console.log("Postorder:", postorder_traversal(root1)); // Expected: [9, 15, 7, 20, 3]

    // Example 2: Single node
    const inorder2 = [1];
    const postorder2 = [1];
    const root2 = buildTree(inorder2, postorder2);
    console.log("Single node:", inorder_traversal(root2));

    // Example 3: Left skewed tree
    const inorder3 = [3, 2, 1];
    const postorder3 = [3, 2, 1];
    const root3 = buildTree(inorder3, postorder3);
    console.log("Left skewed:", inorder_traversal(root3));
}

module.exports = { buildTree, TreeNode };

use std::rc::Rc;
use std::cell::RefCell;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Construct binary tree from inorder and postorder traversal using index tracking.
 *
 * Key insight:
 * - Postorder: left subtree, right subtree, root (last element is always root)
 * - Inorder: left subtree, root, right subtree
 * - Use a pointer to track the current root in postorder (traverse from end to start)
 * - Find root in inorder to split into left and right subtrees
 *
 * Time Complexity: O(n²) in worst case due to linear search for root in inorder
 * Space Complexity: O(h) for recursion call stack where h is height
 */
pub fn build_tree(
    inorder: Vec<i32>,
    postorder: Vec<i32>,
) -> Option<Rc<RefCell<TreeNode>>> {
    if inorder.is_empty() || postorder.is_empty() {
        return None;
    }

    let mut post_idx = postorder.len() as i32 - 1;

    fn build(
        postorder: &[i32],
        inorder: &[i32],
        post_idx: &mut i32,
        in_start: usize,
        in_end: usize,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        /**
         * Recursively build tree by processing postorder from right to left.
         *
         * Args:
         *     in_start, in_end: Range in inorder array
         */

        if in_start > in_end || *post_idx < 0 {
            return None;
        }

        // Current postorder element (processing from end to start)
        let root_val = postorder[*post_idx as usize];
        *post_idx -= 1;

        let mut root = TreeNode::new(root_val);

        // Find root position in inorder
        let mut root_idx = 0;
        for (i, &val) in inorder.iter().enumerate() {
            if val == root_val {
                root_idx = i;
                break;
            }
        }

        // Build right subtree first (postorder: left, right, root)
        // Since we traverse postorder backwards, right comes before left
        root.right = build(postorder, inorder, post_idx, root_idx + 1, in_end);

        // Build left subtree
        root.left = build(
            postorder,
            inorder,
            post_idx,
            in_start,
            if root_idx > 0 { root_idx - 1 } else { root_idx },
        );

        Some(Rc::new(RefCell::new(root)))
    }

    build(
        &postorder,
        &inorder,
        &mut post_idx,
        0,
        inorder.len() - 1,
    )
}

// Helper function for inorder traversal
fn inorder_traversal(node: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    match node {
        None => vec![],
        Some(n) => {
            let n_ref = n.borrow();
            let mut result = inorder_traversal(n_ref.left.clone());
            result.push(n_ref.val);
            result.extend(inorder_traversal(n_ref.right.clone()));
            result
        }
    }
}

// Helper function for postorder traversal
fn postorder_traversal(node: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    match node {
        None => vec![],
        Some(n) => {
            let n_ref = n.borrow();
            let mut result = postorder_traversal(n_ref.left.clone());
            result.extend(postorder_traversal(n_ref.right.clone()));
            result.push(n_ref.val);
            result
        }
    }
}

fn main() {
    // Example 1: [3,9,20,null,null,15,7]
    //     3
    //    / \
    //   9  20
    //      / \
    //     15  7
    let inorder1 = vec![9, 3, 15, 20, 7];
    let postorder1 = vec![9, 15, 7, 20, 3];
    let root1 = build_tree(inorder1, postorder1);

    println!("Inorder: {:?}", inorder_traversal(root1.clone()));   // Expected: [9, 3, 15, 20, 7]
    println!("Postorder: {:?}", postorder_traversal(root1));      // Expected: [9, 15, 7, 20, 3]

    // Example 2: Single node
    let inorder2 = vec![1];
    let postorder2 = vec![1];
    let root2 = build_tree(inorder2, postorder2);
    println!("Single node: {:?}", inorder_traversal(root2));

    // Example 3: Left skewed tree
    let inorder3 = vec![3, 2, 1];
    let postorder3 = vec![3, 2, 1];
    let root3 = build_tree(inorder3, postorder3);
    println!("Left skewed: {:?}", inorder_traversal(root3));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example1() {
        let inorder = vec![9, 3, 15, 20, 7];
        let postorder = vec![9, 15, 7, 20, 3];
        let root = build_tree(inorder, postorder);
        assert_eq!(inorder_traversal(root), vec![9, 3, 15, 20, 7]);
    }

    #[test]
    fn test_single_node() {
        let inorder = vec![1];
        let postorder = vec![1];
        let root = build_tree(inorder, postorder);
        assert_eq!(inorder_traversal(root), vec![1]);
    }
}

package main

import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/*
buildTree constructs a binary tree from inorder and postorder traversal using index tracking.

Key insight:
- Postorder: left subtree, right subtree, root (last element is always root)
- Inorder: left subtree, root, right subtree
- Use a pointer to track the current root in postorder (traverse from end to start)
- Find root in inorder to split into left and right subtrees

Time Complexity: O(n²) in worst case due to linear search for root in inorder
Space Complexity: O(h) for recursion call stack where h is height
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
  if len(inorder) == 0 || len(postorder) == 0 {
    return nil
  }

  postIdx := len(postorder) - 1

  var build func(inStart, inEnd int) *TreeNode
  build = func(inStart, inEnd int) *TreeNode {
    /*
    Recursively build tree by processing postorder from right to left.

    Args:
        inStart, inEnd: Range in inorder array
    */

    if inStart > inEnd || postIdx < 0 {
      return nil
    }

    // Current postorder element (processing from end to start)
    rootVal := postorder[postIdx]
    postIdx--

    root := &TreeNode{Val: rootVal}

    // Find root position in inorder
    rootIdx := -1
    for i := inStart; i <= inEnd; i++ {
      if inorder[i] == rootVal {
        rootIdx = i
        break
      }
    }

    // Build right subtree first (postorder: left, right, root)
    // Since we traverse postorder backwards, right comes before left
    root.Right = build(rootIdx+1, inEnd)

    // Build left subtree
    root.Left = build(inStart, rootIdx-1)

    return root
  }

  return build(0, len(inorder)-1)
}

// Helper function for inorder traversal
func inorderTraversal(node *TreeNode) []int {
  if node == nil {
    return []int{}
  }
  result := inorderTraversal(node.Left)
  result = append(result, node.Val)
  result = append(result, inorderTraversal(node.Right)...)
  return result
}

// Helper function for postorder traversal
func postorderTraversal(node *TreeNode) []int {
  if node == nil {
    return []int{}
  }
  result := postorderTraversal(node.Left)
  result = append(result, postorderTraversal(node.Right)...)
  result = append(result, node.Val)
  return result
}

func main() {
  // Example 1: [3,9,20,null,null,15,7]
  //     3
  //    / \
  //   9  20
  //      / \
  //     15  7
  inorder1 := []int{9, 3, 15, 20, 7}
  postorder1 := []int{9, 15, 7, 20, 3}
  root1 := buildTree(inorder1, postorder1)

  fmt.Println("Inorder:", inorderTraversal(root1))     // Expected: [9 3 15 20 7]
  fmt.Println("Postorder:", postorderTraversal(root1)) // Expected: [9 15 7 20 3]

  // Example 2: Single node
  inorder2 := []int{1}
  postorder2 := []int{1}
  root2 := buildTree(inorder2, postorder2)
  fmt.Println("Single node:", inorderTraversal(root2))

  // Example 3: Left skewed tree
  inorder3 := []int{3, 2, 1}
  postorder3 := []int{3, 2, 1}
  root3 := buildTree(inorder3, postorder3)
  fmt.Println("Left skewed:", inorderTraversal(root3))
}

Common mistakes

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

"""
Solution for Construct Binary Tree from Inorder and Postorder Traversal
"""

def solve():
    """Implementation for approach 3 of Construct Binary Tree from Inorder and Postorder Traversal"""
    pass

if __name__ == "__main__":
    print("Solution ready")

#include <bits/stdc++.h>
using namespace std;

// Solution for Construct Binary Tree from Inorder and Postorder Traversal
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

/**
 * Solution for Construct Binary Tree from Inorder and Postorder Traversal
 * Approach 3
 */
public class ConstructBinaryTreeFromInorderAndPostorderTraversalSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

/**
 * Solution for Construct Binary Tree from Inorder and Postorder Traversal
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

/// Solution for Construct Binary Tree from Inorder and Postorder Traversal
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

package main

import "fmt"

// Solution for Construct Binary Tree from Inorder and Postorder Traversal
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Interview Tips

Why HashMap over linear search? Trading O(n) space for O(1) lookups turns an O(n²) algorithm into O(n). Mention this when explaining optimization.
Postorder vs Preorder — Preorder ends with the last element being part of the right subtree; postorder ends with the root. This is the fundamental difference.
Why build right before left in the index approach? Because we traverse postorder backwards (right to left), the right subtree is encountered before the left.
Edge cases to mention: single node, completely left-skewed tree, completely right-skewed tree, identical values in different subtrees (problem guarantees uniqueness).
Follow-up question: How would you solve this if the tree could have duplicate values? (You’d need additional metadata or a different approach.)

Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

Examples

Constraints

Real-World Applications

Complexity Comparison

Which approach should you learn first?

Approach 1: HashMap (Recommended)

Step-by-step Example

Pseudocode

Solution Code

Approach 2: Index Tracking

Step-by-step Example

Pseudocode

Solution Code

Common mistakes

Approach 3: Space-Optimized Variant

Pseudocode

Solution Code

Related Problems

Interview Tips