255. Verify Preorder Sequence in Binary Search Tree

Problem Description

The challenge is to determine whether a given array of unique integers represents the correct preorder traversal of a Binary Search Tree (BST). Preorder traversal of a BST means visiting the nodes in the order: root, left, right. To qualify as a valid BST traversal, the sequence must reflect the BST's structure, where for any node, all the values in the left subtree are less than the node's value, and all the values in the right subtree are greater.

Intuition

For a preorder traversal of a binary search tree, the order of elements would reflect the root being visited first, then the left subtree, and then the right subtree. In a BST, the left subtree contains nodes that are less than the root, and the right subtree contains nodes greater than the root.

The provided solution uses a stack and a variable that keeps track of the last node value we've visited so far when moving towards the right in the tree. Starting with the first value in the preorder traversal, which would be the root of the BST, we consider the following:

1. BST Property: As we iterate through the preorder list, if we encounter a value that is less than the last visited node when turning right, we know that the tree's sequential structure is incorrect.

2. Preorder Traversal Structure: A stack is used to keep track of the traversal path; when we go down left we push onto the stack, and when we turn right we pop from the stack. The top of the stack always contains the parent node we would have to compare with when going right.

3. Switching from Left to Right: Each time we pop from the stack, we update the last value, which symbolizes that all future node values should be larger than this if we are considering the right subtree now.

4. Finally, if we complete the iteration without finding any contradictions to the properties above, we return True indicating that the sequence can indeed be the preorder traversal of a BST.

Throughout the stack manipulation, we are implicitly maintaining the invariant of the BST - that nodes to the left are smaller than root, and nodes to the right are greater.

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

Solution Approach

The implementation of the solution follows a straightforward algorithm that keeps track of the necessary properties of a BST during the traversal sequence:

1. Initialization: A stack stk is created to keep track of ancestors as we traverse the preorder array. A variable last is initialized to negative infinity, representing the minimum constraint of the current subtree node values.

2. Traversal: We iterate through each value x in the preorder array.

3. Validity Check: For every x, we check if x < last. If this condition is met, it means we have encountered a value smaller than the last value after turning right in the tree, which violates the BST property, hence we return False.

4. Updating Stack: While the stack is not empty and the last element (top of the stack) is less than the current value x, we are moving from the left subtree to the right subtree. We pop values from the stack as we are effectively traveling up the tree, and update the last value. The last value now becomes the right boundary for all the subsequent nodes in the subtree.

5. Processing Current Value: After performing the necessary pops (if any), we append the current value x to the stack. This push operation represents the traversal down the left subtree.

6. Termination: If the entire preorder traversal is processed without returning False, it implies that the sequence did not violate any BST properties, and we return True.

The algorithm uses a stack to model the ancestors in the preorder traversal and a variable last to ensure that the BST's right subtree property holds at every step. The simplicity of the solution comes from understanding how the preorder traversal works in conjunction with the BST properties.

Here is the highlighted implementation of the approach:

1class Solution:
2    def verifyPreorder(self, preorder: List[int]) -> bool:
3        stk = []            # [Stack](/problems/stack_intro) for keeping track of the ancestor nodes
4        last = -inf         # Variable to hold the last popped node value as a bound
5        for x in preorder:
6            if x < last:    # If the current node's value is less than last, it violates the BST rule
7                return False
8            while stk and stk[-1] < x:
9                last = stk.pop()  # Update 'last' each time we turn right (encounter a greater value than the top of the stack)
10            stk.append(x)    # Push the current value onto the stack
11        return True          # If all nodes processed without violating BST properties, the sequence is valid

This approach effectively simulates the traversal of a BST while ensuring that both the left and right subtree properties hold throughout the process.

Example Walkthrough

Let's consider a small example to illustrate the solution approach with the following preorder traversal list [5, 2, 1, 3, 6].

1. Initialize the stack stk to an empty list, and last to negative infinity, which will represent the minimum value of the current subtree's nodes.

2. Traverse the preorder list:

   a. Begin with the first element x = 5. Since x is not less than last (which is -inf at this point), we continue and push 5 onto the stack. The stack now looks like [5].

   b. Next element x = 2. It is not less than last, so we push 2 onto the stack. The stack becomes [5, 2].

   c. For element x = 1, again x is not less than last, so we push 1 to the stack. The stack is now [5, 2, 1].

   d. Now x = 3. It's greater than the top of the stack (which is 1), so we pop 1 from the stack, and update last to 1. We continue popping because the top of the stack (2) is still less than 3, update last to 2, and finally push 3 to the stack. Now, the stack is [5, 3].

   e. For the last element x = 6, the top of the stack is 3, which is less than x, so we pop 3 from the stack and the new last is now 3. The stack is [5] and since 5 is less than x, we pop again and update last to 5. Now the stack is empty, and we push 6 to the stack. So, the final stack is [6].

3. Since we have placed all elements onto the stack according to the rules, and have never encountered an element less than last during the process, the iteration completes successfully.

4. The preorder is possible for a BST, so we return True.

The pattern here shows that the stack is used to maintain a path of ancestors while iterating, and last serves as a lower bound for the nodes that can come after turning right, ensuring that subsequent nodes are always greater than any node’s value after turning right. Throughout every step, the BST property was maintained properly.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the preorder traversal list. This is because the code iterates through each element of the preorder list exactly once. During each iteration, both the stack push (stk.append(x)) and pop (stk.pop()) operations are executed at most once per element, which are O(1) operations, therefore not increasing the overall time complexity beyond O(n).

The space complexity of the code is O(n), due to the stack stk that is used to store elements. In the worst-case scenario, the stack could store all the elements of the preorder traversal if they appear in strictly increasing order. However, due to the nature of binary search trees, if the input is a valid BST preorder traversal, the space complexity can be reduced on average, but in the worst case, it still remains O(n).

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