Validate binary tree sorted

Question

Given a binary tree, write a function to determine if it is a valid binary search tree (BST). A valid BST is defined as a binary tree in which all the left subtree nodes are less than the root node, and all the right subtree nodes are greater than the root node. The function should return a boolean value indicating whether the binary tree satisfies the BST property.

Codemia · Accepted Answer

To determine if a binary tree is a valid binary search tree (BST), we can utilize the properties of BSTs: all left subtree nodes must be less than the root node, and all right subtree nodes must be greater than the root node. This suggests a recursive approach where we can validate each node by keeping track of the valid range of values it can take. The underlying pattern here is a depth-first search (DFS) because we will traverse the tree and check the constraints for each node as we go deeper into the tree.

1. Define a helper function that accepts a node and two parameters representing the valid range of values for that node (min_val and max_val).  
2. Start with the root node and set the initial valid range as (-infinity, +infinity).  
3. For each node, check:  
   - If the current 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 an updated max_val (current node's value) and the right child with an updated min_val (current node's value).  
4. If we reach a leaf node (None), return True, indicating that the subtree rooted at this point satisfies the BST properties.  
5. Finally, start the validation from the root node.

**Example:**  
For the binary tree:  
```
     2
    / \
   1   3
```
The root is 2, its left child is 1 (which is less than 2), and its right child is 3 (which is greater than 2). Thus, this tree is a valid BST.

Here is the Python solution implementing the approach discussed:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root: TreeNode) -> bool:
    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 uses a nested helper function to validate each node recursively.

The time complexity of this solution is O(n) because we visit each node in the tree exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack. In the worst case (for a skewed tree), h can be equal to n, but for a balanced tree, it would be O(log n). This approach is efficient given the constraints of the problem.

1. **Empty Tree:** An empty tree should return True because it is considered a valid BST.  
2. **Single Node Tree:** A tree with only one node should also return True.  
3. **Duplicate Values:** If the tree has duplicate values, such as:  
```
     2
    / \
   2   3
```
This should return False because the left child is not less than the root.  
4. **Invalid BST Structures:** Trees that violate the BST properties should return False. For instance:  
```
     5
    / \
   1   4
      / \
     3   6
```
This tree is invalid because 3 is less than 5 but is in the right subtree.

Validate binary tree sorted

PlanetScale

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

PlanetScale 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