Construct Binary Tree from Preorder and Inorder Traversal

class Solution {
public:
    int currentPreorderIndex = 0;
    unordered_map<int, int> indexMap;
    TreeNode* buildSubTree(vector<int>& preorder, int start, int end) {
        if (start > end) return nullptr;
        int rootVal = preorder[currentPreorderIndex++];
        TreeNode* root = new TreeNode(rootVal);
        root->left = buildSubTree(preorder, start, indexMap[rootVal] - 1);
        root->right = buildSubTree(preorder, indexMap[rootVal] + 1, end);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        currentPreorderIndex = 0;
        for (int i = 0; i < inorder.size(); i++) {
            indexMap[inorder[i]] = i;
        }
        return buildSubTree(preorder, 0, preorder.size() - 1);
    }
};

Explore the C++ solution that efficiently constructs a binary tree from preorder and inorder traversal arrays. The key components of this solution involve utilizing recursion and hash mapping to maintain track of indices, which significantly optimizes the search process within the inorder array.

Solution Breakdown:

• Define the class Solution with private members:

  • currentPreorderIndex to keep track of the index for the currently being processed node in the preorder array.
  • indexMap to store the index of each value in the inorder array for quick access.

• Implement the buildSubTree method:

  • This method is responsible for creating the tree recursively. It receives the preorder array and the current subarray bounds (start and end) as parameters.
  • If the start index exceeds the end, return nullptr indicating no subtree is formed.
  • Extract the root value from the preorder array using currentPreorderIndex and increment it.
  • Create a new tree node TreeNode with the root value.
  • Recursively construct the left subtree using indices from start to indexMap[rootVal] - 1.
  • Similarly, construct the right subtree using indices from indexMap[rootVal] + 1 to end.
  • Return the constructed TreeNode.

• Implement the buildTree method:

  • Initialize currentPreorderIndex to 0.
  • Populate indexMap where each key-value pair consists of a value from the inorder array and its corresponding index.
  • Start the recursive construction of the tree by calling buildSubTree with bounds from 0 to preorder.size() - 1.

This approach, leveraging a hash map and recursion, allows for swift and efficient reconstruction of the binary tree without searching the entire inorder array repeatedly for the root element, which makes it time-efficient. This technique greatly reduces the time complexity typically encountered in tree construction problems.

class Solution {
    int preorderPosition;
    Map<Integer, Integer> idxMapInorder;

    public TreeNode constructBinaryTree(int[] preOrder, int[] inOrder) {
        preorderPosition = 0;
        // Create a map from value to its index in inorder
        idxMapInorder = new HashMap<>();
        for (int i = 0; i < inOrder.length; i++) {
            idxMapInorder.put(inOrder[i], i);
        }

        return buildTreeFromPreIn(preOrder, 0, preOrder.length - 1);
    }

    private TreeNode buildTreeFromPreIn(int[] preOrder, int start, int end) {
        // Base condition if no elements are present
        if (start > end) return null;

        // Root is the current element at preorderPosition in preOrder
        int rootVal = preOrder[preorderPosition++];
        TreeNode rootNode = new TreeNode(rootVal);

        // Construct left and right subtree excluding the root's index
        rootNode.left = buildTreeFromPreIn(
            preOrder,
            start,
            idxMapInorder.get(rootVal) - 1
        );
        rootNode.right = buildTreeFromPreIn(
            preOrder,
            idxMapInorder.get(rootVal) + 1,
            end
        );
        return rootNode;
    }
}

The provided Java code implements a solution to construct a binary tree from a given preorder and inorder traversal array. This algorithm involves:

• Initializing a global index to keep track of the current position within the preorder array.
• Creating a hashmap to map each value in the inorder array to its index. This aids in quick look-up for the root nodes in recursive calls.
• Implement the constructBinaryTree method which initializes the necessary data structures and calls a helper method to construct the tree recursively.
• Implementing the buildTreeFromPreIn private method where the actual binary tree is built. In this method:
  • It checks the base case where the start index exceeds the end index, implying that the current subtree is empty.
  • It determines the root node of the current subtree using the current preorder position.
  • Recursively constructs the left subtree by considering the element range before the root element in the inorder traversal.
  • Recursively constructs the right subtree by considering the element range after the root element in the inorder traversal.

The use of hashmap for index tracking optimizes the time complexity, as finding the root's index in the inorder array becomes constant time. This solution is efficient and handles the construction of a binary tree from traversal data effectively.

struct KeyValueMapping {
    int key;
    int value;
    UT_hash_handle hh;
};

struct TreeNode* preorderToInorderTree(int* preorderArray, int* inorderArray,
                                       struct KeyValueMapping** indexMapping,
                                       int* preorderIdx, int leftBoundary, int rightBoundary) {
    if (leftBoundary > rightBoundary) return NULL;
    int rootNodeValue = preorderArray[(*preorderIdx)++];
    struct TreeNode* newRoot = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newRoot->val = rootNodeValue;
    struct KeyValueMapping* found;
    HASH_FIND_INT(*indexMapping, &rootNodeValue, found);
    newRoot->left = preorderToInorderTree(preorderArray, inorderArray, indexMapping, preorderIdx, leftBoundary,
                                          found->value - 1);
    newRoot->right = preorderToInorderTree(preorderArray, inorderArray, indexMapping, preorderIdx,
                                           found->value + 1, rightBoundary);
    return newRoot;
}

struct TreeNode* constructBinaryTree(int* preorder, int preorderLength, int* inorder,
                                     int inorderLength) {
    struct KeyValueMapping* indexMapping = NULL;
    for (int idx = 0; idx < inorderLength; idx++) {
        struct KeyValueMapping* mapEntry =
            (struct KeyValueMapping*)malloc(sizeof(struct KeyValueMapping));
        mapEntry->key = inorder[idx];
        mapEntry->value = idx;
        HASH_ADD_INT(indexMapping, key, mapEntry);
    }
    int rootIndex = 0;
    return preorderToInorderTree(preorder, inorder, &indexMapping, &rootIndex, 0,
                                 inorderLength - 1);
}

The provided C code defines a solution for constructing a binary tree from preorder and inorder traversal arrays. Here's a concise summary of how this process is implemented:

1. Data Structures Used:

   • The KeyValueMapping struct is designed to map the integer keys from the inorder array to their corresponding indices.
   • The TreeNode struct is a node of the tree containing the integer value and pointers to left and right child nodes.

2. Utility Functions and Approach:

   • constructBinaryTree initializes a hash map using UT_hash_handle to record the indices of elements in the inorder array for quick lookup. This function sets up the initial conditions and calls preorderToInorderTree.
   • preorderToInorderTree performs the recursive construction of the binary tree. It uses the preorder array to determine the root node and the index mapping from the inorder array to partition the tree into left and right subtrees.

3. Recursive Construction:

   • Using the next element in the preorder array as the root, the function locates this root in the inorder array using the hash map.
   • It then constructs the entire tree by recursively building the left subtree from the elements before the root in the inorder array and the right subtree from the elements after the root.
   • Recursion ends when the boundaries for the left and right children are invalid, implying that a leaf node is reached.

4. Memory Management:

   • malloc is used for dynamic memory allocation for each tree node and mapping entry, essential for building the tree and mapping structure during execution.

This code is effective for building binary trees when both preorder and inorder traversal lists are known, leveraging hash tables for efficient index lookups, which significantly speeds up the construction process.

var constructBinaryTree = function(preorderList, inorderList) {
    let indexPreorder = 0;
    let mapInorderIndex = new Map();
    
    for (let index = 0; index < inorderList.length; index++) {
        mapInorderIndex.set(inorderList[index], index);
    }
    
    function buildSubTree(start, end) {
        if (start > end) return null;
        
        let rootVal = preorderList[indexPreorder++];
        let treeNode = new TreeNode(rootVal);
        
        treeNode.left = buildSubTree(start, mapInorderIndex.get(rootVal) - 1);
        treeNode.right = buildSubTree(mapInorderIndex.get(rootVal) + 1, end);
        
        return treeNode;
    }
    return buildSubTree(0, preorderList.length - 1);
};

The provided JavaScript solution efficiently constructs a binary tree from its preorder and inorder traversal sequences. The essential element here is the mapping of inorder values to their indices to expedite the reconstruction process. Build a comprehensive map of element indices from the inorderList before inititating the recursive construction of the subtree. The buildSubTree function facilitates the recursive construction using the defined bounds on the current subtree's inorder list, updating the subtree root accordingly each recursive call. A binary tree node is created for each non-null value in the preorderList by referencing the incremented preorder index. This node then becomes a root, with recursive calls to build its left and right children. In summary, the function builds the binary tree by utilizing the provided preorder list for the root node sequence, and the mapped inorder list to split the tree into left and right subtrees recursively. The strategy ensures an efficient and systematic assembly of the binary tree with respect to its specified traversal orders.

class Solution:
    def constructBinaryTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        def construct_subtree(start, end):
            nonlocal index_tracker
            if start > end:
                return None

            root_val = preorder[index_tracker]
            new_node = TreeNode(root_val)

            index_tracker += 1

            new_node.left = construct_subtree(start, value_to_index[root_val] - 1)
            new_node.right = construct_subtree(value_to_index[root_val] + 1, end)

            return new_node

        index_tracker = 0
        value_to_index = {value: idx for idx, value in enumerate(inorder)}

        return construct_subtree(0, len(preorder) - 1)

The Python code provided defines a method to construct a binary tree from given preorder and inorder traversal sequences. The algorithm uses recursive strategy to build the tree and tracks node values through a dictionary that maps each value to its index in the inorder list. Here's how the process generally unfolds:

• A nested function construct_subtree(start, end) is defined, which handles the recursive construction of the binary tree. It takes start and end as parameters to determine the current segment of the inorder traversal to consider.

• The global variable index_tracker is used to keep track of the current index in the preorder list. This helps in picking the root for each subtree being constructed recursively.

• If the start parameter is greater than end, it indicates that the current segment is invalid for a subtree, and thus None is returned, indicating the absence of a node.

• The value of the current root node of the subtree is picked from the preorder list using index_tracker, and a new tree node new_node is created with this root value.

• The recursive calls are made separately for the left and right children of the current root. For the left child, the subtree corresponds to the elements before the root's index in the inorder sequence; for the right child, it follows the root’s index.

• A dictionary value_to_index is created outside the nested function to quickly find the index of any element from the inorder list, which optimizes the process of splitting the inorder list into left and right parts for the recursive calls.

• The construct_subtree function is initially called with the full range of indices from the preorder list as parameters to start the tree construction.

• The final tree root is returned after all recursive calls complete, providing a structured binary tree as specified by the preorder and inorder lists.

This solution effectively builds a binary tree with a time complexity primarily determined by the recursive tree construction and an auxiliary space complexity due to the space allocated for the recursion stack and the dictionary mapping values to indices.