Validate Binary Search Tree - Solution & Explanation
Problem Statement
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
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:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
Approach Overview
Problem 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.
Approach 1: Approach 1: Recursive In-Order Traversal
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.
Complexity
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.
Approach 2: Approach 2: Iterative In-Order Traversal
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.
Complexity
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(h) for the stack where h is tree height.
Approach 3: 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.
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.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Validate Binary Search Tree - Depth First Search - Leetcode 98 • NeetCode • 327,232 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Validate Binary Search Tree easy or hard?
Validate Binary Search Tree Python/Java solution
How to solve Validate Binary Search Tree in O(n)?
What is the best approach for Validate Binary Search Tree?
Is Validate Binary Search Tree asked at Google/Amazon/Meta?
What data structure is used in Validate Binary Search Tree?
What is the time complexity of Validate Binary Search Tree?
Ready to solve this problem?
Practice Validate Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor