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: You’re given the root of a binary tree and need to verify whether it satisfies the rules of a Binary Search Tree (BST). Every node must follow the constraint left subtree < node < right subtree, and this rule must hold for every node in the tree.
Approach 1: Recursive In-Order Traversal (O(n) time, O(h) space)
A key property of a valid BST is that an in-order traversal visits nodes in strictly increasing order. Traverse the tree using recursion: visit the left subtree, process the current node, then visit the right subtree. While traversing, track the value of the previously visited node. If the current node’s value is less than or equal to the previous value, the BST property is violated and the tree is invalid.
This approach works because binary search trees naturally produce sorted output during in-order traversal. The recursion depth depends on the tree height, so the space complexity is O(h), where h is the height of the tree. In balanced trees this is O(log n), but it becomes O(n) in the worst case of a skewed tree. The time complexity remains O(n) because each node is visited exactly once.
Approach 2: Iterative In-Order Traversal (O(n) time, O(h) space)
This version performs the same in-order traversal but replaces recursion with an explicit stack. Start at the root and repeatedly push nodes while moving left until you reach a null node. Pop from the stack, process the node, then move to its right child. During each visit, compare the current value with the previously visited value to ensure the sequence remains strictly increasing.
The iterative approach avoids recursion and gives you more control over the traversal process. It uses a stack to simulate the call stack typically used in depth-first search. Time complexity is still O(n) since every node is pushed and popped once. Space complexity remains O(h) due to the stack storing nodes along the current path from the root to a leaf.
Both approaches rely on the structural property of tree traversal rather than explicitly checking value ranges for every subtree. The sorted in-order sequence provides a simple and reliable validation mechanism.
Recommended for interviews: Recursive in-order traversal is the most common solution interviewers expect because it clearly demonstrates understanding of BST properties and DFS traversal. The iterative version is equally efficient and shows stronger control over stack-based traversal, which can stand out in more advanced interviews.
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.
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.
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(h) for the stack where h is tree height.
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.
Therefore, we use a variable prev to save the last node we traversed. Initially, prev = -∞. Then we recursively traverse the left subtree. If the left subtree is not a binary search tree, we directly return False. Otherwise, we check whether the value of the current node is greater than prev. If not, we return False. Otherwise, we update prev to the value of the current node, and then recursively traverse the right subtree.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive In-Order Traversal | O(n) | O(h) | Standard interview solution. Clean and easy to implement when recursion is acceptable. |
| Iterative In-Order Traversal | O(n) | O(h) | Useful when avoiding recursion or demonstrating explicit stack-based DFS traversal. |
Validate Binary Search Tree - Depth First Search - Leetcode 98 • NeetCode • 313,782 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