#98

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Validate Binary Search Tree

Validate Binary Search Tree problem checks if a binary tree satisfies BST properties using tree traversal and state tracking.

tree depth first search binary search tree binary tree

Problem Statement

Given the root of a binary tree, you need to determine whether the tree is a valid Binary Search Tree (BST). A valid BST is one where for each node, the left subtree contains only nodes with values less than the node’s value, and the right subtree contains only nodes with values greater than the node’s value. This must hold true for every node in the tree.

A Binary Search Tree (BST) must meet these conditions recursively for every node in the tree. You are tasked with traversing the tree while maintaining boundaries that ensure the values of the nodes follow the BST properties. The tree is valid if and only if all nodes satisfy these conditions.

Examples

Example 1

Input: root = [2,1,3]

Output: true

Example details omitted.

Example 2

Input: root = [5,1,4,null,null,3,6]

Output: false

The root node's value is 5 but its right child's value is 4.

Constraints

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

Solution Approach

Tree Traversal with State Tracking

Start by performing a Depth-First Search (DFS) traversal of the binary tree. While traversing, maintain the valid range for each node. The left child must have values smaller than the current node’s value, and the right child must have values larger. Update these ranges recursively as you explore each node. If any node fails this condition, the tree is invalid.

Recursive Approach

Using recursion, for each node, check if it falls within the range set by its ancestors. The range for a left child will be bounded by the node's value from the parent, and for the right child, the upper bound will be the node's value. If the node violates its bounds, the tree is invalid.

Efficient Time and Space Complexity

The time complexity for this approach is O(N), where N is the number of nodes in the tree, as each node is visited 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, if the tree is unbalanced, H could be O(N), but in the best case, it’s O(log N).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(N), where N is the number of nodes, because we visit each node once. The space complexity depends on the height of the tree, O(H), due to the recursion stack. In the worst case (unbalanced tree), this could be O(N), but in a balanced tree, it’s O(log N).

What Interviewers Usually Probe

Do you understand the properties of a valid Binary Search Tree?
Can you explain how recursion helps track valid ranges for nodes?
Will you describe the time and space complexity of this solution?

Common Pitfalls or Variants

Common pitfalls

Not correctly maintaining the range for each node during recursion.
Misunderstanding how the left and right subtrees' valid ranges differ.
Failing to account for edge cases like a tree with only one node.

Follow-up variants

Check if a binary tree is a valid AVL tree (self-balancing binary search tree).
Determine if a binary tree is a valid Binary Search Tree with duplicate values allowed.
Validate a Binary Search Tree using iterative traversal techniques.

FAQ

What makes a binary tree a valid Binary Search Tree?

A Binary Search Tree is valid if, for every node, its left child contains values smaller than the node and the right child contains values greater, with this property recursively applying to every node in the tree.

How does the recursive approach work to validate a BST?

In the recursive approach, each node’s value is validated by ensuring it falls within a valid range that is updated as we traverse down the tree. The left child should be smaller, and the right child should be larger.

What is the time complexity of this problem?

The time complexity is O(N), where N is the number of nodes in the tree, since each node is visited once during the DFS traversal.

Can this solution handle edge cases like empty or single-node trees?

Yes, the solution works for edge cases like an empty tree or a single node. In these cases, the tree is automatically considered valid.

How do you handle unbalanced trees in this problem?

The solution handles unbalanced trees effectively by ensuring that each node’s left and right children respect the required bounds, regardless of the tree's structure.

terminal

Solution

Solution 1: Recursion

We can perform a recursive in-order traversal on the binary tree. If the result of the traversal is strictly ascending, then this tree is a binary search tree.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(root: Optional[TreeNode]) -> bool:
            if root is None:
                return True
            if not dfs(root.left):
                return False
            nonlocal prev
            if prev >= root.val:
                return False
            prev = root.val
            return dfs(root.right)

        prev = -inf
        return dfs(root)

Continue Practicing

#99 recover binary search tree #230 kth smallest element in a bst #235 lowest common ancestor of a binary search tree