Validate binary tree valid BST

Question

Given a binary tree, implement a function to determine if it is a valid binary search tree (BST). A valid BST must satisfy the property that for any node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. The function should return a boolean indicating whether the tree is a valid BST.

Codemia · Accepted Answer

To determine if a binary tree is a valid binary search tree (BST), we need to verify that for every node:
1. All values in the left subtree are less than the node's value.
2. All values in the right subtree are greater than the node's value.

The in-order traversal of a BST should yield a sorted sequence of values. The key pattern here is to use recursion with boundary values to maintain the BST properties as we traverse the tree. This is a depth-first search (DFS) approach, where we check the validity of each node against the constraints defined by its ancestors.

We can implement a recursive function that takes a node and two additional parameters that represent the allowed value range for that node:
1. `min_val`: the minimum value that the current node can have (initially set to negative infinity).
2. `max_val`: the maximum value that the current node can have (initially set to positive infinity).

### Steps:
1. Start with the root node and call the recursive function with `min_val` as negative infinity and `max_val` as positive infinity.
2. For each node, check:
   - If the node's value is less than or equal to `min_val` or greater than or equal to `max_val`, return False.
   - Recursively check the left child with updated `max_val` set to the current node's value.
   - Recursively check the right child with updated `min_val` set to the current node's value.
3. If all nodes satisfy the conditions, return True.

Here's the Python code implementing the approach:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root):
    def validate(node, min_val, max_val):
        if not node:
            return True
        if not (min_val < node.val < max_val):
            return False
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    return validate(root, float('-inf'), float('inf'))
```
This function checks if the binary tree rooted at `root` is a valid BST.

### Time Complexity:
- The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the recursion.

### Space Complexity:
- The space complexity is O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case (a skewed tree), h could be equal to n, but in a balanced tree, it would be O(log n).

1. **Empty Tree**: An empty tree should return True since it trivially satisfies the BST properties.
2. **Single Node Tree**: A tree with only one node should also return True.
3. **Duplicate Values**: The problem does not define how to handle duplicate values, but typically, a BST does not allow duplicates. Thus, if a node has a value equal to its parent node, it should return False.
4. **Skewed Trees**: Both left-skewed and right-skewed trees should be handled correctly, as they are valid BSTs if they adhere to the min/max constraints.

Validate binary tree valid BST

Shopify

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

Shopify 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