Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
[1, 104].-231 <= Node.val <= 231 - 1Problem Overview: Given the root of a binary tree, determine whether it satisfies the properties of a Binary Search Tree (BST). For every node, all values in the left subtree must be smaller and all values in the right subtree must be larger, and this rule must hold recursively for the entire tree.
Approach 1: Recursive In-Order Traversal (O(n) time, O(h) space)
A valid Binary Search Tree produces a strictly increasing sequence when traversed using in-order traversal (left → node → right). Run a recursive Depth-First Search and track the previously visited node value. During traversal, compare the current node with the previous value; if the current value is not greater, the BST property is violated. This approach works because in-order traversal of a BST naturally sorts values. Time complexity is O(n) since every node is visited once, and space complexity is O(h) from the recursion stack, where h is the height of the tree.
This method is clean and commonly expected in interviews. The recursive structure mirrors the natural definition of a binary tree, making the logic easy to reason about.
Approach 2: Iterative In-Order Traversal with Stack (O(n) time, O(h) space)
The same sorted-order insight can be implemented iteratively using a stack. Instead of recursion, push nodes while traversing left until reaching the smallest element. Pop from the stack, compare the node value with the previously processed value, then move to the right subtree. Each node is pushed and popped once, so the total time complexity remains O(n). The stack stores at most the height of the tree, giving O(h) space complexity.
This approach is useful when recursion depth may be large or when you prefer explicit control over the traversal process. The logic mirrors the recursive solution but replaces the call stack with an explicit stack structure.
Recommended for interviews: Recursive in-order traversal is the fastest way to communicate the core BST insight. It shows you understand how BST ordering relates to traversal. The iterative version demonstrates deeper understanding of traversal mechanics and stack simulation. Interviewers usually accept either, but the recursive solution is the most concise and commonly written on the whiteboard.
This approach involves recursively traversing the binary tree in an in-order manner, comparing each node's value with a running minimum and maximum valid value, to ensure the BST properties hold. The initial minimum and maximum allow for any integer value, and they get updated as we traverse the tree.
The validate function checks if the current node's value is within the valid range dictated by min and max. It recursively checks the left subtree with an updated max and the right subtree with an updated min.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes because we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree due to the recursive stack usage.
This approach involves an iterative in-order traversal using a stack to ensure non-decreasing order of node values. We iterate through the nodes using the stack and at each step, compare the current node's value with the last visited node.
This solution uses a manual stack (implemented as a struct in C) to perform in-order traversal. We keep track of the previous node's value to ensure all nodes are in increasing order.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(h) for the stack where h is tree height.
| Approach | Complexity |
|---|---|
| Approach 1: Recursive In-Order Traversal | Time Complexity: O(n), where n is the number of nodes because we visit each node exactly once. |
| Approach 2: Iterative In-Order Traversal | Time Complexity: O(n) since each node is visited once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive In-Order Traversal | O(n) | O(h) | Cleanest solution. Best for interviews and when recursion depth is manageable. |
| Iterative In-Order Traversal (Stack) | O(n) | O(h) | When avoiding recursion or implementing traversal explicitly using a stack. |
Validate Binary Search Tree - Depth First Search - Leetcode 98 • NeetCode • 257,702 views views
Watch 9 more video solutions →Practice Validate Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor