What is the time complexity of Construct Binary Tree from Inorder and Postorder Traversal?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Construct Binary Tree from Inorder and Postorder Traversal?

This problem uses Array, Hash Table, Divide and Conquer, Tree, Binary Tree. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Construct Binary Tree from Inorder and Postorder Traversal?

The last element in the `postorder` array is always the root of the (sub)tree. The `inorder` array allows us to determine the structure of the left and right subtrees. Elements to the left of the root in `inorder` belong to the left subtree, and elements to the right belong to the right subtree.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

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

Q: How to solve Construct Binary Tree from Inorder and Postorder Traversal?

The solution uses a recursive approach. We start with the root node, which is the last element in the `postorder` array. We find the index of this root node in the `inorder` array. This index divides the `inorder` array into left and right subtrees. We then recursively build the left and right subtrees using the corresponding portions of the `inorder` and `postorder` arrays. A hash map (or array in C) is used to efficiently find the index of the root in the `inorder` array, making the lookup O(1).

Q: Which companies ask LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal in interviews?

This problem is frequently asked at Adobe.

Construct Binary Tree from Inorder and Postorder Traversal - Complete Solution Guide

Construct Binary Tree from Inorder and Postorder Traversal is LeetCode problem 106, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree . Example 1: Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7] Example 2: Input: inorder = [-1], postorder = [-1] Output: [-1] Constraints: 1 <= inorder.length <= 3000 postorder.length == inorder.length -3000 <= inorder[i], postorder[i] <= 3000 inorder and post

Detailed Explanation

The problem asks us to reconstruct a binary tree given its inorder and postorder traversals. The inorder traversal lists nodes in the order: left subtree, root, right subtree. The postorder traversal lists nodes in the order: left subtree, right subtree, root. We need to return the root of the constructed tree. The input consists of two integer arrays, `inorder` and `postorder`, representing these traversals. The problem guarantees that the values are unique and that both traversals belong to the same tree.

Solution Approach

The solution uses a recursive approach. We start with the root node, which is the last element in the `postorder` array. We find the index of this root node in the `inorder` array. This index divides the `inorder` array into left and right subtrees. We then recursively build the left and right subtrees using the corresponding portions of the `inorder` and `postorder` arrays. A hash map (or array in C) is used to efficiently find the index of the root in the `inorder` array, making the lookup O(1).

Step-by-Step Algorithm

Step 1: If either `inorder` or `postorder` is empty, return `None` (or `NULL`).
Step 2: Create a hash map (or array in C) to store the index of each value in the `inorder` array. This allows for O(1) lookup of the root's position in `inorder`.
Step 3: Initialize a `post_idx` variable to the last index of the `postorder` array. This variable keeps track of the current root node being processed.
Step 4: Define a recursive helper function that takes the left and right indices of the `inorder` array as input. Base case: if the left index is greater than the right index, it indicates that we have reached an empty subtree and should return `None` (or `NULL`).
Step 5: In the helper function, create a new `TreeNode` with the value from `postorder[post_idx]`. Decrement `post_idx`.
Step 6: Find the index of the root value in the `inorder` array using the hash map.
Step 7: Recursively call the helper function to build the right subtree, passing the indices from `inorder_idx + 1` to `in_right`. Assign the result to the right child of the current node. Crucially, the right subtree is built *before* the left subtree, because `post_idx` is decrementing from the *end* of the `postorder` array.
Step 8: Recursively call the helper function to build the left subtree, passing the indices from `in_left` to `inorder_idx - 1`. Assign the result to the left child of the current node.
Step 9: Return the current node.

Key Insights

The last element in the `postorder` array is always the root of the (sub)tree.
The `inorder` array allows us to determine the structure of the left and right subtrees. Elements to the left of the root in `inorder` belong to the left subtree, and elements to the right belong to the right subtree.
Recursion is a natural approach to solve this problem because we can recursively build the left and right subtrees.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Divide and Conquer, Tree, Binary Tree.

Companies

Asked at: Adobe.

Construct Binary Tree from Inorder and Postorder Traversal | LeetCode 106

Medium

Array Hash Table Divide and Conquer Tree Binary Tree

Time: O(n)Space: O(n)

Solution Code

Available in:

/**
 * Definition for a binary 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;
 *     }
 * }
 */
class Solution {
    private int post_idx;
    private int[] inorder;
    private int[] postorder;
    private HashMap<Integer, Integer> inorder_map = new HashMap<Integer, Integer>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        this.post_idx = postorder.length - 1;

        for (int i = 0; i < inorder.length; i++) {
            inorder_map.put(inorder[i], i);
        }

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

    private TreeNode helper(int in_left, int in_right) {
        if (in_left > in_right) {
            return null;
        }

        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);
        post_idx--;

        int inorder_idx = inorder_map.get(root_val);

        root.right = helper(inorder_idx + 1, in_right);
        root.left = helper(in_left, inorder_idx - 1);

        return root;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 106: Construct Binary Tree from Inorder and Postorder Traversal - Detailed explanation and solution approaches.

Topics

Array Hash Table Divide and Conquer Tree Binary Tree

Companies

Adobe

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:106

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: If either `inorder` or `postorder` is empty, return `None` (or `NULL`).
2
Step 2: Create a hash map (or array in C) to store the index of each value in the `inorder` array. This allows for O(1) lookup of the root's position in `inorder`.
3
Step 3: Initialize a `post_idx` variable to the last index of the `postorder` array. This variable keeps track of the current root node being processed.
4
Step 4: Define a recursive helper function that takes the left and right indices of the `inorder` array as input. Base case: if the left index is greater than the right index, it indicates that we have reached an empty subtree and should return `None` (or `NULL`).
5
Step 5: In the helper function, create a new `TreeNode` with the value from `postorder[post_idx]`. Decrement `post_idx`.
6
Step 6: Find the index of the root value in the `inorder` array using the hash map.
7
Step 7: Recursively call the helper function to build the right subtree, passing the indices from `inorder_idx + 1` to `in_right`. Assign the result to the right child of the current node. Crucially, the right subtree is built *before* the left subtree, because `post_idx` is decrementing from the *end* of the `postorder` array.
8
Step 8: Recursively call the helper function to build the left subtree, passing the indices from `in_left` to `inorder_idx - 1`. Assign the result to the left child of the current node.
9
Step 9: Return the current node.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n) because each node is visited once to construct the tree, and the index lookup in the `inorder` array is done in O(1) time using the hash map. The space complexity is O(n) because we need to store the `inorder` array indices in the hash map (or array in C) and, in the worst case, the recursion stack could be as deep as the number of nodes in the tree (e.g., in a skewed tree).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Approach

It is possible to solve this problem iteratively using a stack. The stack keeps track of the potential roots to be processed. It mimics the recursive calls but without the function call overhead.

Time: O(n)Space: O(n)

Trade-offs: Iterative approach avoids recursion call overhead, but might be less intuitive to understand. Debugging can be more challenging.

✨

Key Insights

1The last element in the `postorder` array is always the root of the (sub)tree.
2The `inorder` array allows us to determine the structure of the left and right subtrees. Elements to the left of the root in `inorder` belong to the left subtree, and elements to the right belong to the right subtree.
3Recursion is a natural approach to solve this problem because we can recursively build the left and right subtrees.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty input arrays. The solution handles this by returning `None` (or `NULL`) if either `inorder` or `postorder` is empty.
Edge case 2: Single node tree. The solution correctly handles this case because the recursion will terminate when `in_left` and `in_right` point to the same element.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly determining the sub-array boundaries for the left and right subtrees in the `inorder` array. The `inorder_idx` needs to be handled carefully to define the ranges.

✗Common mistake 2: Forgetting to decrement `post_idx` after creating a new node. This leads to using the same root value multiple times.

✗Common mistake 3: Building the left subtree before the right subtree. Since we are traversing the `postorder` array from the end, we need to construct the right subtree first.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Parsing expression trees. Expression trees represent mathematical or logical expressions, and tree traversals are used to evaluate or transform these expressions. This problem demonstrates how to construct a tree from its traversals.

🏦Real-world scenario 2: Compiler design. Compilers use tree structures to represent the structure of the code being compiled. Understanding how to construct and manipulate trees is essential for compiler development.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Construct Binary Tree from Inorder and Postorder Traversal"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?