Given the root of a binary tree, determine if it is a valid binary search tree. A Validate Binary Search Tree requires specific conditions to be true. The left subtree of a node must contain only nodes with keys strictly less than the node's key. The right subtree of a node must contain only nodes with keys strictly greater than the node's key. Furthermore, both the left and right subtrees must also be valid binary search trees themselves.
Example 1
Input: root = [2,1,3]
Output: true
Explanation: The root node is 2. The left child is 1, which is less than 2. The right child is 3, which is greater than 2. All conditions are satisfied.
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node is 5. However, its right child is 4, which is strictly less than 5. This violates the property of a binary search tree.
Brute Force Approach
When checking if a tree is valid, it is not enough to just compare a parent node with its direct left and right children. A node deep in the right subtree might be greater than its immediate parent, but it still must be greater than the main root node of the entire tree.
Consider a security checkpoint system where people are sorted into different zones based on their clearance levels. Once you are directed to the left wing, your clearance level has a strict maximum limit. If you are then directed to the right room within that wing, you gain a minimum limit, but your maximum limit from the previous step still applies.
Similarly, we give each node a valid numerical range. As we travel left, we update the maximum allowed value. As we travel right, we update the minimum allowed value. If any node falls out of its allowed range, the entire tree is invalid.
Algorithm
Start at the root node and define the initial valid range from negative infinity to positive infinity.
Check if the current node is empty. If it is, return true because an empty tree is valid.
Check if the current node value falls strictly within the allowed minimum and maximum boundaries.
If the value is out of bounds, return false.
Recursively call the function for the left child, updating the maximum boundary to the current node value.
Recursively call the function for the right child, updating the minimum boundary to the current node value.
Return true only if both left and right subtree checks return true.
Dry Run
Validate Binary Search Tree Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;/* Definition for a binary tree node */struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};/* C++ program to implement Validate Binary Search Tree */class Solution {public: /* Validates if the tree is a BST by checking against a valid range */ bool isValidBST(TreeNode* root) { return checkBST(root, LONG_MIN, LONG_MAX); }private: /* Helper function to maintain the minimum and maximum boundaries */ bool checkBST(TreeNode* node, long minVal, long maxVal) { /* Base case: an empty subtree is always valid */ if (node == nullptr) { return true; } /* Node value must be strictly within the allowed range */ if (node->val <= minVal || node->val >= maxVal) { return false; } /* Traverse left updating maximum, traverse right updating minimum */ return checkBST(node->left, minVal, node->val) && checkBST(node->right, node->val, maxVal); }};/* Driver code starts */int main() { Solution sol; TreeNode* root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); bool result = sol.isValidBST(root); if (result) { cout << "true"; } else { cout << "false"; } return 0;}Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes in the tree, because we visit each node exactly once.
Space Complexity: O(H), where H is the height of the tree, because of the memory used by the recursion stack.
Optimal Approach
Why the previous approach is inefficient The recursive range approach is highly efficient in time complexity. However, dealing with maximum and minimum infinity values can sometimes cause integer overflow issues in specific programming languages if not handled carefully.
What improvement this approach brings This approach avoids passing extreme minimum and maximum values down the tree. Instead, it relies on a core property of binary search trees: an inorder traversal of a valid BST will always process the nodes in strictly increasing order.
Think of reading books on a shelf arranged in alphabetical order. You process them one by one from left to right. If you ever pick up a book that comes alphabetically before the one you just read, you immediately know the shelf is disarrayed. By performing an inorder traversal which means visiting the left child, then the root, then the right child, we can maintain a reference to the previously visited node. If the current node is not greater than the previous node, the tree is invalid.
Algorithm
Create a variable to store the previously visited node, initially set to null.
Perform a recursive inorder traversal starting from the root.
Traverse the left subtree. If it returns false, propagate the false result upwards.
Check the current node against the previously visited node. If the current node value is less than or equal to the previous value, return false.
Update the previously visited node to be the current node.
Traverse the right subtree and return its result.
Dry Run
Validate Binary Search Tree Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;/* Definition for a binary tree node */struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};/* C++ program to implement Validate Binary Search Tree */class Solution {private: TreeNode* prev = nullptr;public: /* Validates if the tree is a BST using inorder traversal */ bool isValidBST(TreeNode* root) { /* Base case: empty tree is valid */ if (root == nullptr) { return true; } /* Check left subtree recursively */ if (!isValidBST(root->left)) { return false; } /* Compare current node with the previously visited node */ if (prev != nullptr && root->val <= prev->val) { return false; } /* Update previous node to current before moving right */ prev = root; /* Check right subtree recursively */ return isValidBST(root->right); }};/* Driver code starts */int main() { Solution sol; TreeNode* root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); bool result = sol.isValidBST(root); if (result) { cout << "true"; } else { cout << "false"; } return 0;}Complexity Analysis
Time Complexity: O(N), because the traversal visits each node in the tree exactly once.
Space Complexity: O(H), where H is the height of the tree, representing the memory used on the call stack during the recursion.
Interview follow-up Questions
No, based on standard definitions, the left subtree must contain only strictly smaller keys, and the right subtree strictly larger keys. Duplicate values are typically not allowed.
Be the first to add a comment.