1008. Construct Binary Search Tree from Preorder Traversal


Problem Description

This problem requires constructing a Binary Search Tree (BST) from a given array of integers that represent the preorder traversal of the BST. A BST is a type of binary tree where each node satisfies the constraint that all the values in its left subtree are less than the node's value, and all the values in its right subtree are greater than the node's value.

Given the nature of preorder traversal, the first element in the traversal represents the root of the tree. The elements following the root are then divided into two subarrays: the left subtree elements and the right subtree elements. The left subtree contains all elements less than the root's value, and the right subtree contains all elements greater than the root's value. These subarrays are used recursively to construct the left and right subtrees.

Intuition

To construct the BST from the preorder sequence, we make use of the above-mentioned property of BSTs: all left descendants are less than the node, and all right descendants are greater.

Here's the approach to solving the problem:

  1. Treat the first value as the root node since we're given a preorder traversal array.
  2. Split the remaining elements into two groups: one for the left subtree and one for the right subtree. The left subtree consists of all elements less than the root's value, whereas the right subtree includes all elements more significant than the root's value.
  3. Recursively apply these steps to both the left and right groups to construct the entire tree.

The solution makes use of a recursive function, dfs, which creates a node for each call using the first element in the current array slice as the node's value. It then uses binary search to find the boundary between the left and right children nodes. Finally, it constructs the subtree by recursively calling the same function on the appropriate subarrays for left and right children.

By breaking down the problem in this way and using recursion, we can recreate the BST that corresponds to the given preorder traversal.

Learn more about Stack, Tree, Binary Search Tree, Binary Tree and Monotonic Stack patterns.

Solution Approach

The solution is implemented in Python, and it uses a recursive depth-first search (DFS) approach to reconstruct the Binary Search Tree (BST). The code block defines a helper function dfs that performs the main logic of constructing the BST.

Let's explore the key parts of the implementation:

Recursive DFS Function:

  • The dfs function takes the preorder array slice representing the current subtree it is processing.
  • It first checks if the preorder array is empty. If so, it returns None, as there are no more nodes to construct in this subtree.
  • It then creates the root node of the current subtree using the first value of the preorder array as TreeNode(preorder[0]).

Binary Search to Split the Array:

  • Next, within the dfs function, we use binary search to determine the boundary between the left and right children nodes.
  • This boundary is the index of the first element in preorder that is greater than the root's value. We use a loop that performs a binary search to find this boundary efficiently.
  • Once found, the elements from preorder[1:left] will be all the elements that belong to the left subtree (values less than the root's value), and the elements from preorder[left:] will be those that belong to the right subtree (values greater than the root’s value).

Recursion to Build Subtrees:

  • The dfs function calls itself twice recursively to construct the left and right subtrees. The left subtree is created using the elements before the found boundary, and the right subtree is created using the elements after the boundary.

Putting It All Together:

  • The initial call to dfs is made with the entire preorder array, and it returns the root of the BST constructed.
  • As the recursive calls proceed, smaller slices of the preorder array are passed down to construct each subtree until the entire BST is built.

The Recursive Process in Steps:

  1. The function is initially called with the full preorder array. The first element is treated as the root node.
  2. Use binary search within the remaining items to split them into left and right subtrees based on their value in relation to the root's value.
  3. Recursively call dfs with the left subtree elements to construct the left subtree. This call will continue to split and build left and right subtrees until the base case (empty array slice) is reached.
  4. Recursively call dfs with the right subtree elements to do the same for the right subtree.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the preorder traversal array [8, 5, 1, 7, 10, 12]. We want to reconstruct the BST that results in this preorder sequence.

Step-by-Step Reconstruction:

  1. Call dfs function with the full preorder array ([8, 5, 1, 7, 10, 12]). The first element 8 is chosen as the root node.
  2. We perform a binary search to split the array into elements that are less than 8 ([5, 1, 7]) for the left subtree, and elements that are greater ([10, 12]) for the right subtree.
  3. The left subtree call to dfs uses [5, 1, 7]. Here, 5 is the root of the left subtree.
  4. Binary search on [1, 7] splits it into [1] for the left subtree and [7] for the right, both relative to the new root node 5.
  5. The recursion continues, with dfs called with [1], making 1 a leaf node (as it has no further elements to process), and similarly, dfs called with [7] making 7 a leaf node on the right of node 5.
  6. Meanwhile, for the right subtree, dfs is called with [10, 12]. The root node for this subtree is 10, with no left children (since there are no elements less than 10) and a right child node to be created from [12].
  7. dfs called with [12] makes 12 a leaf node, being the right child of node 10.

Final BST Structure:

The final BST, reconstructed from the preorder array [8, 5, 1, 7, 10, 12], will look like this:

1        8
2       /  \
3      5   10
4     / \    \
5    1   7    12

Each recursive call to dfs constructs a part of this tree, resulting in the BST that reflects the given preorder sequence.

Solution Implementation

1class TreeNode:
2    # Definition for a binary tree node.
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8
9class Solution:
10    def bstFromPreorder(self, preorder):
11        """
12        Construct a binary search tree from a list of values representing
13        preorder traversal.
14
15        :param preorder: List[int] - A list of integers representing the preorder traversal of a BST.
16        :return: Optional[TreeNode] - The root node of the constructed BST.
17        """
18
19        def construct_bst_from_preorder(preorder_values):
20            # Base case: if the list is empty, return None as there's no tree to construct.
21            if not preorder_values:
22                return None
23
24            # The first value in the preorder list is the root of the BST.
25            root = TreeNode(preorder_values[0])
26            left_index, right_index = 1, len(preorder_values)
27
28            # Find the boundary between left and right subtrees.
29            while left_index < right_index:
30                mid = (left_index + right_index) // 2  # Using floor division for Python 3.
31                if preorder_values[mid] > preorder_values[0]:
32                    # If the mid value is greater than the root's value,
33                    # it belongs to the right subtree.
34                    right_index = mid
35                else:
36                    # Otherwise, it belongs to the left subtree.
37                    left_index = mid + 1
38
39            # Recursively build the left and right subtrees.
40            root.left = construct_bst_from_preorder(preorder_values[1:left_index])
41            root.right = construct_bst_from_preorder(preorder_values[left_index:])
42          
43            # Return the root of the constructed subtree.
44            return root
45
46        # Call the recursive helper function to build the BST from preorder traversal.
47        return construct_bst_from_preorder(preorder)
48
1class Solution {
2    public TreeNode bstFromPreorder(int[] preorder) {
3        // Start constructing binary search tree from the preorder array
4        return constructBST(preorder, 0, preorder.length - 1);
5    }
6
7    /**
8     * Helper method to recursively construct a BST given a preorder traversal range.
9     *
10     * @param preorder The array storing the preorder traversal of the BST.
11     * @param startIndex The start index in the array for the current subtree.
12     * @param endIndex The end index in the array for the current subtree.
13     * @return The constructed TreeNode that is the root of this subtree.
14     */
15    private TreeNode constructBST(int[] preorder, int startIndex, int endIndex) {
16        // Base case: when the start index is greater than end index or out of bounds
17        if (startIndex > endIndex || startIndex >= preorder.length) {
18            return null;
19        }
20      
21        // The first element of the current range is the root of this subtree
22        TreeNode root = new TreeNode(preorder[startIndex]);
23
24        // Find the boundary between left and right subtrees
25        // The first bigger element than the root will be the root of the right subtree
26        int splitIndex = findSplitIndex(preorder, startIndex, endIndex, preorder[startIndex]);
27
28        // Construct the left subtree
29        root.left = constructBST(preorder, startIndex + 1, splitIndex - 1);
30
31        // Construct the right subtree
32        root.right = constructBST(preorder, splitIndex, endIndex);
33
34        return root;
35    }
36
37    /**
38     * Helper method to find the index of the first element greater than the root's value.
39     * 
40     * @param preorder The array storing the preorder traversal.
41     * @param startIndex The start index for the search.
42     * @param endIndex The end index for the search.
43     * @param rootValue The value of the root node.
44     * @return The index of the first element bigger than rootValue, or the end of the range if not found.
45     */
46    private int findSplitIndex(int[] preorder, int startIndex, int endIndex, int rootValue) {
47        int left = startIndex + 1;
48        int right = endIndex + 1;
49        while (left < right) {
50            int mid = (left + right) >> 1; // Equivalent to (left + right) / 2 but faster
51            if (preorder[mid] > rootValue) {
52                right = mid;
53            } else {
54                left = mid + 1;
55            }
56        }
57        // left is the index of the first element greater than rootValue, or endIndex + 1
58        return left;
59    }
60}
61
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Constructs a binary search tree from preorder traversal values.
16    TreeNode* bstFromPreorder(vector<int>& preorder) {
17        return constructBST(preorder, 0, preorder.size() - 1);
18    }
19
20    // Helper function to construct BST from preorder traversal in range [start, end].
21    TreeNode* constructBST(vector<int>& preorder, int start, int end) {
22        // Base case: If start index is greater than end or start is out of bounds.
23        if (start > end || start >= preorder.size()) return nullptr;
24
25        // Create a new tree node with the current value.
26        TreeNode* root = new TreeNode(preorder[start]);
27
28        // Initialize the positions to partition the preorder vector.
29        int leftTreeEnd = start + 1, rightTreeStart = end + 1;
30
31        // Binary search to find the first value greater than root's value, to differentiate left and right subtrees.
32        while (leftTreeEnd < rightTreeStart) {
33            int mid = (leftTreeEnd + rightTreeStart) >> 1; // Equivalent to divide by 2
34            if (preorder[mid] > preorder[start])
35                rightTreeStart = mid; // Adjust the end of the left subtree
36            else
37                leftTreeEnd = mid + 1; // Adjust the start of the right subtree
38        }
39
40        // Recursively construct left and right subtrees.
41        root->left = constructBST(preorder, start + 1, leftTreeEnd - 1);
42        root->right = constructBST(preorder, leftTreeEnd, end);
43
44        return root;
45    }
46};
47
1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    // TreeNode constructor takes a value and optional child nodes
8    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
9        this.val = val === undefined ? 0 : val;
10        this.left = left === undefined ? null : left;
11        this.right = right === undefined ? null : right;
12    }
13}
14
15// This function builds a binary search tree from a preorder traversal
16function bstFromPreorder(preorder: number[]): TreeNode | null {
17    // Length of the preorder traversal
18    const length = preorder.length;
19    // Initialize the next array to track the next greater element's index
20    const nextGreaterIndex = new Array(length);
21    // Stack to help find the next greater element
22    const stack: number[] = [];
23
24    // Iterate backwards through the preorder array to populate nextGreaterIndex
25    for (let i = length - 1; i >= 0; i--) {
26        // Pop elements from the stack until the current element is greater
27        while (stack.length > 0 && preorder[stack[stack.length - 1]] < preorder[i]) {
28            stack.pop();
29        }
30        // Assign the index of the next greater element or the length if not found
31        nextGreaterIndex[i] = stack.length > 0 ? stack[stack.length - 1] : length;
32        // Push the current index onto the stack
33        stack.push(i);
34    }
35
36    // Recursive function to build the tree
37    const buildTree = (leftIndex: number, rightIndex: number): TreeNode | null => {
38        // If the indices are the same, we've reached a leaf node, return null
39        if (leftIndex >= rightIndex) {
40            return null;
41        }
42        // Create the root TreeNode with the value from preorder traversal
43        // The left child is built from the elements immediately after the root
44        // The right child is built from elements after the left subtree
45        return new TreeNode(
46            preorder[leftIndex],
47            buildTree(leftIndex + 1, nextGreaterIndex[leftIndex]),
48            buildTree(nextGreaterIndex[leftIndex], rightIndex)
49        );
50    };
51
52    // Start building the tree from the first element
53    return buildTree(0, length);
54}
55
56// Example usage
57// const preorder = [8, 5, 1, 7, 10, 12];
58// const tree = bstFromPreorder(preorder);
59// This will build the corresponding BST from the given preorder array
60

Time and Space Complexity

The provided code builds a binary search tree from its preorder traversal sequence. Let's analyze the time and space complexity.

Time Complexity

The time complexity of the code is O(n log n) in the average case and O(n^2) in the worst case. Here's why:

  • The dfs() function is invoked for each element of the preorder sequence once, and within each call, it performs a binary search to split the left and right subtrees, which takes O(log n) time in the best and average case due to the binary search condition (preorder[mid] > preorder[0]).
  • However, if the tree is skewed (i.e., every node only has one child), the binary search degrades into a linear scan at each insertion, as there will be no early termination of the binary search loop (while left < right). In this case, each insertion takes O(n) time, giving us O(n^2) complexity over n insertions.

Overall, assuming the tree is balanced or nearly balanced, we would expect average time complexity to be O(n log n). In the worst case, for a skewed tree, it would be O(n^2).

Space Complexity

The space complexity can be considered in two parts: the recursion call stack space and the space used to store the tree itself.

  • Recursion Call Stack Space: In the average case, the binary tree will be somewhat balanced, and the maximum depth of the recursion stack would be O(log n). In the worst case of a completely skewed tree (e.g., a linked list), the space complexity of the recursion would be O(n).
  • Space for the Tree itself: Independently of the call stack, the space required to store the tree is O(n) since we need to allocate a node for every element in the input array.

Thus, the overall space complexity is O(n), including both the recursion stack space in the average scenario (O(log n)) and the space used to store the tree nodes (O(n)). In the worst case, regarding the call stack, it could be O(n), but the dominant term remains the tree storage, so we remain at a total space complexity of O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄