algoadvance

Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

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.

Clarifying Questions:

  1. Unique Values: Are the values in the tree nodes unique?
    • Yes, each value in the tree nodes is unique.
  2. Valid Traversals: Can we assume that the given preorder and inorder arrays are valid and represent the same tree?
    • Yes, both arrays are guaranteed to represent the same binary tree.
  3. Input Constraints: Are there any constraints on the number of nodes?
    • The constraints are not specified, but we can assume typical constraints for LeetCode problems, such as the length of arrays being reasonable (e.g., up to 10,000).

Strategy:

  1. Preorder Traversal: The first element is the root.
  2. Inorder Traversal: Elements to the left of the root are in the left subtree, and elements to the right of the root are in the right subtree.

Steps to Construct the Tree:

  1. Identify the root from the first element of preorder.
  2. Locate the root in inorder to determine the boundary of left and right subtrees.
  3. Recursively repeat the process for left and right subtrees.

Helper Data Structures:

Code Implementation:

#include <vector>
#include <unordered_map>

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

class Solution {
public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        std::unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i;
        }
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorder_map);
    }
    
private:
    TreeNode* buildTreeHelper(const std::vector<int>& preorder, int preStart, int preEnd,
                              const std::vector<int>& inorder, int inStart, int inEnd,
                              std::unordered_map<int, int>& inorder_map) {
        if (preStart > preEnd || inStart > inEnd) return nullptr;
        
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        
        int rootIndexInorder = inorder_map[rootVal];
        int leftTreeSize = rootIndexInorder - inStart;
        
        root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize,
                                     inorder, inStart, rootIndexInorder - 1, inorder_map);
        root->right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd,
                                      inorder, rootIndexInorder + 1, inEnd, inorder_map);
        return root;
    }
};

Time Complexity:

Overall Time Complexity: O(n).

This approach ensures that we efficiently construct the binary tree from the preorder and inorder traversal arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI