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.
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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def isValidBST(self, root: TreeNode) -> bool:
9 def validate(node, low=-float('inf'), high=float('inf')):
10 if not node:
11 return True
12 if not (low < node.val < high):
13 return False
14 return (validate(node.left, low, node.val) and
15 validate(node.right, node.val, high))
16
17 return validate(root)The function validate checks the validity of the current node and recursively validates its subtrees by narrowing the valid range for node values.
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.
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(h) for the stack where h is tree height.
1#include <stack>
2#include <limits.h>
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 bool isValidBST(TreeNode* root) {
14 std::stack<TreeNode*> stack;
15 TreeNode* current = root;
16 long prevVal = LONG_MIN;
17
18 while (!stack.empty() || current != nullptr) {
19 while (current != nullptr) {
20 stack.push(current);
21 current = current->left;
22 }
23 current = stack.top(); stack.pop();
24 if (current->val <= prevVal)
25 return false;
26 prevVal = current->val;
27 current = current->right;
28 }
29 return true;
30 }
31};This solution uses the built-in stack in C++ to facilitate in-order traversal and checks that each node's value is larger than that of the last visited node to ensure non-decreased order.