Construct Binary Tree from inorder and preorder

Problem Overview

The given problem on LeetCode is titled "Construct Binary Tree from Preorder and Inorder Traversal." The task is to construct a binary tree from its preorder and inorder traversal sequences.

The problem URL: Construct Binary Tree from Preorder and Inorder Traversal

Understanding the Problem

Binary trees are a fundamental data structure in computer science. Each tree has a root node and potentially many levels of additional nodes that branch out from the root. Traversing these trees can be performed in various ways. Two of these ways are preorder and inorder traversals:

• Preorder Traversal: Visit the root node first, then recursively visit the left subtree, followed by the right subtree.
• Inorder Traversal: Recursively visit the left subtree first, then visit the root node, and finally the right subtree.

Given two sequences, one representing the preorder traversal and the other representing the inorder traversal of a tree, the goal is to reconstruct the original binary tree from these sequences.

Key DSA Concepts and Theory

1. Binary Trees

A binary tree is a recursive data structure where each node can have at most two children. Understanding the binary tree is crucial for solving this problem as our task is to reconstruct such a structure from traversal orders.

2. Depth-First Traversals

Depth-First Traversals are vital for understanding the mechanics of preorder and inorder sequences. They help in visualizing how nodes are visited and thus aid in constructing the tree back.

3. Recursive Tree Building

The task leverages recursive approaches to build the tree. Recursion simplifies the tree reconstruction by breaking the problem into smaller, more manageable subproblems, working with one node at a time until the entire structure is rebuilt.

Solution Approach

To tackle this problem, we need to leverage the properties of preorder and inorder traversals:

1. Identify the Root: The root of the tree can immediately be identified from the preorder list as it is the first element.
2. Locate the Root in Inorder List: By finding the root in the inorder list, we can identify the left and right subtrees.
3. Recursive Construction: Recursively apply the above steps to construct the left and right substrees.

C++ Implementation

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

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

class Solution {
    std::unordered_map<int, int> inorderIndexMap;
    int preorderIndex = 0;

    TreeNode* buildTreeHelper(std::vector<int>& preorder, int left, int right) {
        if (left > right) return NULL;

        // Root value from preorder traversal
        int rootValue = preorder[preorderIndex++];
        
        TreeNode* root = new TreeNode(rootValue);
        int inorderIndex = inorderIndexMap[rootValue];

        // Recursively build left and right subtrees
        root->left = buildTreeHelper(preorder, left, inorderIndex - 1);
        root->right = buildTreeHelper(preorder, inorderIndex + 1, right);

        return root;
    }

public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        // Store the index of each value from inorder in a map
        for (int i = 0; i < inorder.size(); ++i) {
            inorderIndexMap[inorder[i]] = i;
        }
        return buildTreeHelper(preorder, 0, inorder.size() - 1);
    }
};

Java Implementation

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

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

class Solution {
    private Map<Integer, Integer> inorderIndexMap;
    private int preorderIndex;

    private TreeNode buildTreeHelper(int[] preorder, int left, int right) {
        if (left > right) {
            return null;
        }
        
        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);

        int inorderIndex = inorderIndexMap.get(rootValue);

        root.left = buildTreeHelper(preorder, left, inorderIndex - 1);
        root.right = buildTreeHelper(preorder, inorderIndex + 1, right);

        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        preorderIndex = 0;
        return buildTreeHelper(preorder, 0, inorder.length - 1);
    }
}

Time and Space Complexity Analysis

• Time Complexity: The time complexity is O(n), where n is the number of nodes in the tree. This is because we process each node exactly once.

• Space Complexity: The space complexity is also O(n). This involves the storage for the hashmap to keep indices of inorder values and recursion stack space.

Common Mistakes to Avoid

1. Ignoring base cases: Ensure that the recursive function includes the correct base condition to terminate, preventing infinite recursion.
2. Incorrect index boundaries: Pay careful attention to index boundaries while slicing the preorder and inorder lists.

Similar Problems on LeetCode

• 105. Construct Binary Tree from Preorder and Inorder Traversal
• 106. Construct Binary Tree from Inorder and Postorder Traversal

Additional Resources and References

• Binary Trees on Wikipedia
• Binary Tree Traversals on GeeksforGeeks
• Recursive Algorithms in Trees

By understanding these traversal sequences and recursive building techniques, you'll efficiently solve similar binary tree construction problems.