Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Construct Binary Tree from Preorder and Inorder Traversal 🧠

LeetCode Link: Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal

Description: Given two integer arrays preorder and inorder representing the preorder and inorder traversal of a binary tree, construct the binary tree.

Intuition: In a preorder traversal, the root node is visited first, followed by the left subtree and then the right subtree. In an inorder traversal, the left subtree is visited first, followed by the root node and then the right subtree. We can utilize these properties to construct the binary tree.

Approach:

  1. Create a helper function, buildTreeHelper, to construct the binary tree recursively.
  2. In the buildTreeHelper function:
  • Check if the preorder array is empty. If so, return nullptr.
  • Extract the root value from the preorder array and create a new node.
  • Find the index of the root value in the inorder array.
  • Split the inorder array into left and right subtrees based on the root index.
  • Recursively call the buildTreeHelper function for the left subtree using the corresponding sections of the preorder and inorder arrays.
  • Recursively call the buildTreeHelper function for the right subtree using the corresponding sections of the preorder and inorder arrays.
  • Assign the left and right subtrees to the root node.
  • Return the root node.
  1. Call the buildTreeHelper function with the entire preorder and inorder arrays.
  2. Return the constructed binary tree.

Time Complexity: The time complexity of the approach is O(n), where n is the number of nodes in the binary tree. We visit each node once during the construction.

💾 Space Complexity: The space complexity is O(n), where n is the number of nodes in the binary tree. This is the space used by the recursive call stack.

Solutions 💡

Cpp 💻

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
  public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return buildTreeHelper(preorder, inorder, 0, 0, inorder.size() - 1);
    }

  private:
    TreeNode *buildTreeHelper(vector<int> &preorder, vector<int> &inorder, int preStart, int inStart, int inEnd) {
        if (preStart >= preorder.size() || inStart > inEnd) {
            return nullptr;
        }

        int rootVal = preorder[preStart];
        TreeNode *root = new TreeNode(rootVal);
        int rootIndex;

        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        int leftSize = rootIndex - inStart;
        root->left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, rootIndex - 1);
        root->right = buildTreeHelper(preorder, inorder, preStart + leftSize + 1, rootIndex + 1, inEnd);
        return root;
    }
};

Python 🐍

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None

        root_val = preorder.pop(0)
        root = TreeNode(root_val)
        root_index = inorder.index(root_val)

        root.left = self.buildTree(preorder, inorder[:root_index])
        root.right = self.buildTree(preorder, inorder[root_index + 1 :])

        return root