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

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

What data structures are used to solve Construct Binary Tree from Preorder and Inorder 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 Preorder and Inorder Traversal?

Insight 1: The first element in the `preorder` array is always the root of the tree (or a subtree). Insight 2: The `inorder` array allows us to determine the structure of the left and right subtrees relative to the root. All elements to the left of the root value in the `inorder` array form the left subtree, and all elements to the right form the right subtree.

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

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode 105 Solution

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

The solution uses a recursive approach. The `preorder` array is used to determine the root node, and the `inorder` array is used to determine the structure of the left and right subtrees. We maintain an index into the `preorder` array to track the current root node. We also use a hash map to store the indices of each value in the `inorder` array. This allows us to quickly find the index of the root node in the `inorder` array, which is needed to determine the size of the left and right subtrees. The recursive function `build` is then called to construct the left and right subtrees, using the appropriate subarrays of the `preorder` and `inorder` arrays.

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

This problem is frequently asked at Adobe, Apple, Bloomberg, Meta, Salesforce and 4 more companies.

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

Construct Binary Tree from Preorder and Inorder Traversal is LeetCode problem 105, 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 preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree . Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1] Constraints: 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder and inorder c

Detailed Explanation

The problem asks us to reconstruct a binary tree given its preorder and inorder traversals. Preorder traversal visits the root node first, then the left subtree, then the right subtree. Inorder traversal visits the left subtree, then the root node, then the right subtree. The input consists of two integer arrays, `preorder` and `inorder`, representing these traversals. The output should be the root of the constructed binary tree. The constraints ensure that the input is valid, including that the traversals represent the same tree, and the values are unique.

Solution Approach

The solution uses a recursive approach. The `preorder` array is used to determine the root node, and the `inorder` array is used to determine the structure of the left and right subtrees. We maintain an index into the `preorder` array to track the current root node. We also use a hash map to store the indices of each value in the `inorder` array. This allows us to quickly find the index of the root node in the `inorder` array, which is needed to determine the size of the left and right subtrees. The recursive function `build` is then called to construct the left and right subtrees, using the appropriate subarrays of the `preorder` and `inorder` arrays.

Step-by-Step Algorithm

Step 1: Check for an empty input. If either `preorder` or `inorder` is empty, return `null` (or `nullptr` in C++, `NULL` in C).
Step 2: Create a hash map (`inorder_map`) to store the indices of each value in the `inorder` array. This allows for O(1) lookup of the index of a value in the `inorder` array.
Step 3: Initialize a `preorder_index` to 0. This variable will keep track of the next root value in the `preorder` array.
Step 4: Define a recursive function `build(in_left, in_right)`. This function takes the left and right indices of the current subarray of the `inorder` array as input.
Step 5: In the `build` function, check if `in_left > in_right`. If so, it means there are no more nodes in the current subtree, so return `null`.
Step 6: Create a new `TreeNode` with the value at `preorder[preorder_index]`. Increment `preorder_index`.
Step 7: Find the index of the root value in the `inorder_map`. This is `inorder_root_index = inorder_map[root_val]`.
Step 8: Recursively call `build` to construct the left subtree. The left subtree consists of the elements in the `inorder` array from `in_left` to `inorder_root_index - 1`. `root.left = build(in_left, inorder_root_index - 1);`
Step 9: Recursively call `build` to construct the right subtree. The right subtree consists of the elements in the `inorder` array from `inorder_root_index + 1` to `in_right`. `root.right = build(inorder_root_index + 1, in_right);`
Step 10: Return the newly created `root` node.
Step 11: Call the `build` function with the initial range of the `inorder` array (0 to `inorder.length - 1`).
Step 12: Return the result of the `build` function.

Key Insights

Insight 1: The first element in the `preorder` array is always the root of the tree (or a subtree).
Insight 2: The `inorder` array allows us to determine the structure of the left and right subtrees relative to the root. All elements to the left of the root value in the `inorder` array form the left subtree, and all elements to the right form the right subtree.
Insight 3: Recursion is a natural fit for solving this problem because we can break down the problem of constructing the entire tree into smaller subproblems of constructing 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, Apple, Bloomberg, Meta, Salesforce, Snowflake, Tesla, TikTok, Yahoo.

Construct Binary Tree from Preorder and Inorder Traversal | LeetCode 105

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 preorderIndex = 0;
    private int[] preorder;
    private int[] inorder;
    private HashMap<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
            return null;
        }

        this.preorder = preorder;
        this.inorder = inorder;

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

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

    private TreeNode build(int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }

        int rootVal = preorder[preorderIndex];
        TreeNode root = new TreeNode(rootVal);
        preorderIndex++;

        int inorderRootIndex = inorderMap.get(rootVal);

        root.left = build(inLeft, inorderRootIndex - 1);
        root.right = build(inorderRootIndex + 1, inRight);

        return root;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 105: Construct Binary Tree from Preorder and Inorder Traversal - Detailed explanation and solution approaches.

Topics

Array Hash Table Divide and Conquer Tree Binary Tree

Companies

AdobeAppleBloombergMetaSalesforceSnowflakeTeslaTikTok

Stats

Difficulty:Medium

Languages:4

Companies:9

Problem #:105

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

12 steps

1
Step 1: Check for an empty input. If either `preorder` or `inorder` is empty, return `null` (or `nullptr` in C++, `NULL` in C).
2
Step 2: Create a hash map (`inorder_map`) to store the indices of each value in the `inorder` array. This allows for O(1) lookup of the index of a value in the `inorder` array.
3
Step 3: Initialize a `preorder_index` to 0. This variable will keep track of the next root value in the `preorder` array.
4
Step 4: Define a recursive function `build(in_left, in_right)`. This function takes the left and right indices of the current subarray of the `inorder` array as input.
5
Step 5: In the `build` function, check if `in_left > in_right`. If so, it means there are no more nodes in the current subtree, so return `null`.
6
Step 6: Create a new `TreeNode` with the value at `preorder[preorder_index]`. Increment `preorder_index`.
7
Step 7: Find the index of the root value in the `inorder_map`. This is `inorder_root_index = inorder_map[root_val]`.
8
Step 8: Recursively call `build` to construct the left subtree. The left subtree consists of the elements in the `inorder` array from `in_left` to `inorder_root_index - 1`. `root.left = build(in_left, inorder_root_index - 1);`
9
Step 9: Recursively call `build` to construct the right subtree. The right subtree consists of the elements in the `inorder` array from `inorder_root_index + 1` to `in_right`. `root.right = build(inorder_root_index + 1, in_right);`
10
Step 10: Return the newly created `root` node.
11
Step 11: Call the `build` function with the initial range of the `inorder` array (0 to `inorder.length - 1`).
12
Step 12: Return the result of the `build` function.

💡

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 created and processed exactly once. The hash map lookup takes O(1) on average. The space complexity is O(n) because the hash map stores all the `inorder` values, and in the worst case the call stack for the recursion could be O(n) deep. If the tree is balanced, the recursive call stack could be O(log n), but in the skewed tree case, it's O(n).

📖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

An iterative solution using a stack can also be implemented, although it's generally more complex to understand and implement than the recursive approach.

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

Trade-offs: While the iterative approach avoids the overhead of recursion, it is more difficult to understand and implement. The recursive approach is generally preferred for its clarity and conciseness.

✨

Key Insights

1Insight 1: The first element in the `preorder` array is always the root of the tree (or a subtree).
2Insight 2: The `inorder` array allows us to determine the structure of the left and right subtrees relative to the root. All elements to the left of the root value in the `inorder` array form the left subtree, and all elements to the right form the right subtree.
3Insight 3: Recursion is a natural fit for solving this problem because we can break down the problem of constructing the entire tree into smaller subproblems of constructing 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 correctly handles this case by returning `null` when either `preorder` or `inorder` is empty.
Edge case 2: Single-node tree. The algorithm works correctly for a single-node tree because the recursion will stop when `in_left > in_right`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly calculating the indices for the left and right subtrees. It's crucial to use the `inorder_map` to determine the correct boundaries for the recursive calls.

✗Common mistake 2: Forgetting to increment the `preorder_index`. This will result in an infinite loop or incorrect tree construction.

✅

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: This algorithm is used in compilers and interpreters to construct abstract syntax trees (ASTs) from code.

🏦Real-world scenario 2: Representing hierarchical data structures, such as file systems or organizational charts, in a tree format.

💡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

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

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

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

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 14, 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

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

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

@AlgoMasterJul 7

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

@InterviewProJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Construct Binary Tree from Preorder and Inorder 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?