Construct a BST from a preorder traversal

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The problem of constructing a Binary Search Tree (BST) from preorder traversal is a classic problem that frequently appears in both coding interviews and competitive programming. In this problem, you are given an array that represents the preorder traversal of a BST, and your task is to rebuild the BST and return its root node.

Problem Statement: Given an array of integers that represents a preorder traversal of a BST, construct and return the BST.

Example:

  • Input: preorder = [8, 5, 1, 7, 10, 12]
  • Output: The root node of the reconstructed BST.

Understanding the Problem

In preorder traversal, each node is visited before its children, i.e., it follows the order: Node -> Left subtree -> Right subtree. Given this order, the first element in the array will always be the root of the tree. The problem asks us to leverage this property to reconstruct the BST from the given array efficiently.

Key Observations:

  • The first element is always the root.
  • The subsequent elements will form the left or right subtree based on their value compared to the root.
  • All nodes in the left subtree of a BST are lesser than the root, while all nodes in the right subtree are greater.

Understanding these characteristics of BSTs helps in strategizing an efficient construction method.

Key DSA Concepts and Theory

Binary Search Tree Properties

  1. Node Values:
    • Left child < Parent node
    • Right child > Parent node
  2. Traversal Techniques:
    • Preorder: Root, Left, Right
    • Inorder: Left, Root, Right
    • Postorder: Left, Right, Root

Preorder Traversal

Preorder traversal can be particularly handy while constructing or cloning a tree because it gives us direct access to the root node before any descendant nodes.

BST Construction from Preorder:

Constructing a BST from a preorder traversal involves using the properties of BST and the traversal order to determine the placement of each node. The construction can be optimized by maintaining constraints for what values can be inserted where, which is an effective way to replicate the BST structure.

Solution Approach

The task is to construct a BST based on the preorder traversal, ensuring nodes adhere to the BST rules. We will use an index pointer to iterate through the preorder list and a range of permissible values to guide the node placements.

Detailed Steps:

  1. Initialize: Start with an index pointer at the first element and set its value as the root node.
  2. Recursive Construction:
    • For each node, recursively construct the left subtree with values lesser than the current node.
    • Construct the right subtree with values greater than the current node.
  3. Boundaries:
    • Use the characteristics of BST to decide valid ranges for left and right subtree nodes.

Code Implementation

C++ Solution

#include <vector>
#include <limits.h>

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

class Solution {
public:
    TreeNode* bstFromPreorder(std::vector<int>& preorder) {
        int index = 0;
        return helper(preorder, index, INT_MIN, INT_MAX);
    }
    
private:
    TreeNode* helper(std::vector<int>& preorder, int& index, int lower, int upper) {
        if (index == preorder.size()) return nullptr;
        
        int val = preorder[index];
        if (val < lower || val > upper) return nullptr;
        
        index++;
        TreeNode* root = new TreeNode(val);
        root->left = helper(preorder, index, lower, val);  // Values less than `val`
        root->right = helper(preorder, index, val, upper); // Values greater than `val`
        return root;
    }
};

Java Solution

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

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        return construct(preorder, new int[]{0}, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private TreeNode construct(int[] preorder, int[] index, int lower, int upper) {
        if (index[0] == preorder.length) return null;
        
        int val = preorder[index[0]];
        if (val < lower || val > upper) return null;
        
        index[0]++;
        TreeNode root = new TreeNode(val);
        root.left = construct(preorder, index, lower, val);
        root.right = construct(preorder, index, val, upper);
        return root;
    }
}

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed once.
  • Space Complexity: O(n), for the call stack in the recursive solution which can grow up to O(n) in the worst case (skewed tree).

Common Mistakes to Avoid

  • Incorrect Range Management: Ensuring the node values fall within the correct bounds for the left and right subtrees is crucial. Failing to update and maintain these can lead to incorrect tree structures.
  • Preorder Index Management: Incrementing the index at incorrect positions can lead to missed nodes or duplicate nodes in subtrees.

Similar Problems on LeetCode

Additional Resources and References