Jobs

Interviews

Discussions

Verify Preorder Sequence in Binary Search Tree

Medium

Asked by:

63 views

Topics:

ArraysStacksTrees

Given an array of integers preorder, which represents the preorder traversal of a BST (binary search tree), check if it is a valid preorder traversal sequence.

Assume that the values of the BST are distinct.

Example 1:

Input: preorder = [5,2,1,3,6]
Output: true

Example 2:

Input: preorder = [5,2,6,1,3]
Output: false

Constraints:

1 <= preorder.length <= 10⁴
0 <= preorder[i] <= 10⁴
The values of preorder are unique.

Try coding it in LeetCode

Verify Preorder Sequence in Binary Search Tree

Medium

Asked by:

63 views

Topics:

ArraysStacksTrees

Given an array of integers preorder, which represents the preorder traversal of a BST (binary search tree), check if it is a valid preorder traversal sequence.

Assume that the values of the BST are distinct.

Example 1:

Input: preorder = [5,2,1,3,6]
Output: true

Example 2:

Input: preorder = [5,2,6,1,3]
Output: false

Constraints:

1 <= preorder.length <= 10⁴
0 <= preorder[i] <= 10⁴
The values of preorder are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values within the `preorder` array? Can I assume it will fit within the integer range?
Can the input array `preorder` be empty or null? If so, what should I return?
Are all the values in the `preorder` array guaranteed to be unique, as stated in the problem description?
Could you provide an example of a valid `preorder` array and its corresponding BST, or an invalid `preorder` array and an explanation of why it is invalid?
Are there any specific constraints on the height or structure of the BST implied by the problem statement, beyond the fact that it's a BST?

Brute Force Solution

Approach

The basic idea is to explore all possible binary search trees that can be constructed from the given sequence. We check if any of these trees satisfy the preorder property. If even one such tree exists, we know the sequence is a valid preorder traversal for some binary search tree.

Here's how the algorithm would work step-by-step:

Try splitting the sequence into a left subtree and a right subtree at every possible point.
For each split, pretend the left part represents the preorder traversal of the left subtree, and the right part represents the preorder traversal of the right subtree.
Recursively check if the left and right parts can form valid binary search trees. This means repeating the splitting process for each of these subtrees.
Also check if the split maintains the binary search tree property. This means every number in the left subtree should be smaller than the root, and every number in the right subtree should be greater than the root.
If, after checking all possible splits, you find one where both the left and right subtrees are valid binary search trees (following the preorder property) and the binary search tree property is maintained, then the original sequence is a valid preorder traversal.
If none of the splits result in valid binary search trees, the original sequence is invalid.

Code Implementation

def verify_preorder_brute_force(preorder):
    def is_valid_preorder(sequence):
        if not sequence:
            return True

        root_value = sequence[0]

        # Iterate through all possible split points
        for split_index in range(1, len(sequence) + 1):
            left_subtree = sequence[1:split_index]
            right_subtree = sequence[split_index:]

            # Check if all values in the left subtree are smaller than the root
            is_left_subtree_valid = all(value < root_value for value in left_subtree)
            
            # Check if all values in the right subtree are greater than the root
            is_right_subtree_valid = all(value > root_value for value in right_subtree)
            
            # Recursively check if left and right subtrees are valid
            if is_left_subtree_valid and is_right_subtree_valid:
                
                # Check if both subtrees are valid BSTs based on preorder traversal
                if is_valid_preorder(left_subtree) and is_valid_preorder(right_subtree):
                    return True

        return False

    return is_valid_preorder(preorder)

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm considers every possible split of the input preorder sequence of size n into left and right subtrees. For each element, we potentially iterate through the remaining elements to find a suitable split point. This means that for each of the n elements, we perform a comparison that takes, on average, n/2 operations. Thus, the total number of operations becomes approximately n * n/2. Therefore, the overall time complexity is O(n^2).

Space Complexity

O(N) – The dominant space complexity stems from the recursive calls. In the worst-case scenario, the recursion might go as deep as the number of elements in the preorder sequence, N, if the binary search tree is skewed (e.g., a linked list). Each recursive call adds a new frame to the call stack. Therefore, the maximum depth of the call stack and, consequently, the auxiliary space used, is proportional to N.

Optimal Solution

Approach

The key idea is to maintain a lower bound, representing the smallest value that any right subtree node can have. We traverse the sequence, checking if each element is greater than the lower bound; if it is, it could be a valid node in the Binary Search Tree (BST).

Here's how the algorithm would work step-by-step:

Imagine you're building the BST node by node, following the sequence order.
Keep track of a 'floor' or lower limit; this is the smallest value that the right subtree of the last processed node can have. Initially, there is no lower limit.
For each number in the sequence, check if it's bigger than the current lower limit. If it's smaller, the sequence isn't a valid preorder traversal for a BST.
If the number is valid (bigger than the lower limit), try to add it to the current 'path' of nodes you're building.
If you encounter a number that's bigger than a previous number in your 'path', it means you're starting the right subtree of that previous number.
When that happens, update the lower limit to the value of that previous number (since anything to the right must be at least that big), and keep going to see if future values could be subtrees of future values.
After processing the sequence, if you did not encounter invalid preorder, then return valid.

Code Implementation

def verify_preorder(preorder):
    lower_bound = float('-inf')
    stack_of_smaller_nodes = []

    for node_value in preorder:
        # If the current value is less than the lower bound, it's invalid.
        if node_value < lower_bound:
            return False

        # Pop nodes from the stack until we find a larger value.
        while stack_of_smaller_nodes and node_value > stack_of_smaller_nodes[-1]:
            # This node is the parent of the right subtree, so set lower bound.
            lower_bound = stack_of_smaller_nodes.pop()

        # Push the current node onto the stack.
        stack_of_smaller_nodes.append(node_value)

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. Inside the loop, operations like comparison and potentially updating the lower bound happen in constant time, O(1). The key part is that while we conceptually maintain a 'path' of nodes, we're not revisiting nodes or performing nested iterations related to the size of this 'path'; it's more of a stack-like operation. Therefore, the time complexity is directly proportional to the size of the input array, resulting in O(n).

Space Complexity

O(N) – The algorithm maintains a 'path' of nodes using an implicit stack. In the worst-case scenario, where the input array 'preorder' is a strictly decreasing sequence, each element could be added to this stack before any right subtrees are encountered. Therefore, the maximum size of this implicit stack, and thus the auxiliary space used, is proportional to the number of nodes N in the input sequence, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return true, as an empty tree is a valid BST and its preorder traversal is an empty sequence.
Single element array	Return true, as a single node is a valid BST.
Array with two elements, valid increasing order	Handle the case where the second element is greater than the first, representing a right child.
Array with two elements, invalid decreasing order	Handle the case where the second element is less than the first, representing a left child.
Array with numbers in strictly decreasing order	The input violates the BST property, so the solution should return false after comparing against lower bound.
Array with numbers in strictly increasing order	Represents a right-skewed BST, should be handled correctly by the algorithm and return true.
Large input array exceeding memory or stack limits with recursion	Iterative solutions are preferred to prevent stack overflow errors with large datasets; a stack data structure can efficiently store the lower bound.
Integer overflow potential when comparing large values	Use appropriate data types (long) or consider using a relative comparison to avoid overflow when comparing the values against the lower bound.

Empty input array

How to Handle:

Return true, as an empty tree is a valid BST and its preorder traversal is an empty sequence.

Single element array

How to Handle:

Return true, as a single node is a valid BST.

Array with two elements, valid increasing order

How to Handle:

Handle the case where the second element is greater than the first, representing a right child.

Array with two elements, invalid decreasing order

How to Handle:

Handle the case where the second element is less than the first, representing a left child.

Array with numbers in strictly decreasing order

How to Handle:

The input violates the BST property, so the solution should return false after comparing against lower bound.

Array with numbers in strictly increasing order

How to Handle:

Represents a right-skewed BST, should be handled correctly by the algorithm and return true.

Large input array exceeding memory or stack limits with recursion

How to Handle:

Iterative solutions are preferred to prevent stack overflow errors with large datasets; a stack data structure can efficiently store the lower bound.

Integer overflow potential when comparing large values

How to Handle:

Use appropriate data types (long) or consider using a relative comparison to avoid overflow when comparing the values against the lower bound.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values within the `preorder` array? Can I assume it will fit within the integer range?
Can the input array `preorder` be empty or null? If so, what should I return?
Are all the values in the `preorder` array guaranteed to be unique, as stated in the problem description?
Could you provide an example of a valid `preorder` array and its corresponding BST, or an invalid `preorder` array and an explanation of why it is invalid?
Are there any specific constraints on the height or structure of the BST implied by the problem statement, beyond the fact that it's a BST?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Try splitting the sequence into a left subtree and a right subtree at every possible point.
For each split, pretend the left part represents the preorder traversal of the left subtree, and the right part represents the preorder traversal of the right subtree.
Recursively check if the left and right parts can form valid binary search trees. This means repeating the splitting process for each of these subtrees.
Also check if the split maintains the binary search tree property. This means every number in the left subtree should be smaller than the root, and every number in the right subtree should be greater than the root.
If, after checking all possible splits, you find one where both the left and right subtrees are valid binary search trees (following the preorder property) and the binary search tree property is maintained, then the original sequence is a valid preorder traversal.
If none of the splits result in valid binary search trees, the original sequence is invalid.

Code Implementation

def verify_preorder_brute_force(preorder):
    def is_valid_preorder(sequence):
        if not sequence:
            return True

        root_value = sequence[0]

        # Iterate through all possible split points
        for split_index in range(1, len(sequence) + 1):
            left_subtree = sequence[1:split_index]
            right_subtree = sequence[split_index:]

            # Check if all values in the left subtree are smaller than the root
            is_left_subtree_valid = all(value < root_value for value in left_subtree)
            
            # Check if all values in the right subtree are greater than the root
            is_right_subtree_valid = all(value > root_value for value in right_subtree)
            
            # Recursively check if left and right subtrees are valid
            if is_left_subtree_valid and is_right_subtree_valid:
                
                # Check if both subtrees are valid BSTs based on preorder traversal
                if is_valid_preorder(left_subtree) and is_valid_preorder(right_subtree):
                    return True

        return False

    return is_valid_preorder(preorder)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're building the BST node by node, following the sequence order.
Keep track of a 'floor' or lower limit; this is the smallest value that the right subtree of the last processed node can have. Initially, there is no lower limit.
For each number in the sequence, check if it's bigger than the current lower limit. If it's smaller, the sequence isn't a valid preorder traversal for a BST.
If the number is valid (bigger than the lower limit), try to add it to the current 'path' of nodes you're building.
If you encounter a number that's bigger than a previous number in your 'path', it means you're starting the right subtree of that previous number.
When that happens, update the lower limit to the value of that previous number (since anything to the right must be at least that big), and keep going to see if future values could be subtrees of future values.
After processing the sequence, if you did not encounter invalid preorder, then return valid.

Code Implementation

def verify_preorder(preorder):
    lower_bound = float('-inf')
    stack_of_smaller_nodes = []

    for node_value in preorder:
        # If the current value is less than the lower bound, it's invalid.
        if node_value < lower_bound:
            return False

        # Pop nodes from the stack until we find a larger value.
        while stack_of_smaller_nodes and node_value > stack_of_smaller_nodes[-1]:
            # This node is the parent of the right subtree, so set lower bound.
            lower_bound = stack_of_smaller_nodes.pop()

        # Push the current node onto the stack.
        stack_of_smaller_nodes.append(node_value)

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return true, as an empty tree is a valid BST and its preorder traversal is an empty sequence.
Single element array	Return true, as a single node is a valid BST.
Array with two elements, valid increasing order	Handle the case where the second element is greater than the first, representing a right child.
Array with two elements, invalid decreasing order	Handle the case where the second element is less than the first, representing a left child.
Array with numbers in strictly decreasing order	The input violates the BST property, so the solution should return false after comparing against lower bound.
Array with numbers in strictly increasing order	Represents a right-skewed BST, should be handled correctly by the algorithm and return true.
Large input array exceeding memory or stack limits with recursion	Iterative solutions are preferred to prevent stack overflow errors with large datasets; a stack data structure can efficiently store the lower bound.
Integer overflow potential when comparing large values	Use appropriate data types (long) or consider using a relative comparison to avoid overflow when comparing the values against the lower bound.

Empty input array

How to Handle:

Return true, as an empty tree is a valid BST and its preorder traversal is an empty sequence.

Single element array

How to Handle:

Return true, as a single node is a valid BST.

Array with two elements, valid increasing order

How to Handle:

Handle the case where the second element is greater than the first, representing a right child.

Array with two elements, invalid decreasing order

How to Handle:

Handle the case where the second element is less than the first, representing a left child.

Array with numbers in strictly decreasing order

How to Handle:

The input violates the BST property, so the solution should return false after comparing against lower bound.

Array with numbers in strictly increasing order

How to Handle:

Represents a right-skewed BST, should be handled correctly by the algorithm and return true.

Large input array exceeding memory or stack limits with recursion

How to Handle:

Iterative solutions are preferred to prevent stack overflow errors with large datasets; a stack data structure can efficiently store the lower bound.

Integer overflow potential when comparing large values

How to Handle:

Use appropriate data types (long) or consider using a relative comparison to avoid overflow when comparing the values against the lower bound.