Validate array valid BST

Question

Given an array of integers, determine if it can represent the level-order traversal of a binary search tree (BST). The function should return true if the array satisfies the properties of a BST, and false otherwise. Consider edge cases such as empty arrays or arrays with a single element.

Codemia · Accepted Answer

To determine if an array can represent the level-order traversal of a binary search tree (BST), we need to ensure that the elements satisfy the BST properties. Specifically, for any given node, all elements in the left subtree must be less than the node's value, and all elements in the right subtree must be greater. This problem can be approached using a BFS-like method, where we keep track of the permissible range for each node based on its position in the level order traversal. The key is to maintain the boundaries for valid values as we traverse the array.

1. Start with the entire range of valid values for the root (negative infinity to positive infinity). 
2. Use a queue to facilitate the BFS traversal, where each entry contains the index of the current node and its valid range (min, max). 
3. For each node in the queue, check if the next nodes in the array respect the valid range. 
   - If the next node is less than the current node's value, it belongs to the left subtree; update the max boundary. 
   - If the next node is greater, it belongs to the right subtree; update the min boundary. 
4. Continue this process until either all nodes are processed or an invalid condition is found. 
5. If all nodes respect the BST properties, return true; otherwise, return false.

**Example:** For the array [5, 3, 8, 1, 4, 7, 9]: 
- Starting with (5, -inf, inf), enqueue (3, -inf, 5) and (8, 5, inf). 
- Next, for (3, -inf, 5), enqueue (1, -inf, 3) and (4, 3, 5). 
- Continue this until the array is fully processed.

Here is the Python solution implementing the above approach:
```python
from collections import deque

def is_valid_BST(level_order):
    if not level_order:
        return True  # Empty array is valid

queue = deque([(0, float('-inf'), float('inf'))])  # (index, min_val, max_val)

while queue:
        index, min_val, max_val = queue.popleft()
        if index >= len(level_order):
            continue
        value = level_order[index]
        if not (min_val < value < max_val):
            return False
        # Enqueue left and right children
        queue.append((2 * index + 1, min_val, value))  # Left child index
        queue.append((2 * index + 2, value, max_val))  # Right child index

return True
```
This code checks each node against its valid range and enqueues its potential children.

The time complexity of this solution is O(n), where n is the number of elements in the array. We visit each node exactly once during the BFS traversal. The space complexity is also O(n) due to the queue storing nodes. In the worst case, if all nodes are enqueued, we would use space proportional to the number of nodes. This is efficient given the constraints of the problem.

1. **Empty Array:** An empty array should return true, as it can be considered a valid BST. 
2. **Single Element:** An array with one element should also return true since a single node is a valid BST. 
3. **Duplicates:** If the array contains duplicates, it cannot represent a valid BST, so it should return false. 
4. **Invalid BST Representation:** Arrays such as [5, 3, 8, 4, 1] should return false since the left subtree conditions are violated. 
5. **Large Values:** Ensure the solution can handle large integers, including Python's inherent support for large integers.

Validate array valid BST

Workday

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Workday Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string