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.
1function TreeNode(val, left = null, right = null) {
2 this.val = (val===undefined ? 0 : val);
3 this.left = (left===undefined ? null : left);
4 this.right = (right===undefined ? null : right);
5}
6
7var isValidBST = function(root) {
8 const validate = (node, min, max) => {
9 if (!node) return true;
10 if (node.val <= min || node.val >= max) return false;
11 return validate(node.left, min, node.val) &&
12 validate(node.right, node.val, max);
13 };
14 return validate(root, -Infinity, Infinity);
15};This solution uses a helper function to traverse and check the BST conditions by ensuring each node falls within the valid integer range based on its position in the tree.
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.
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 stack = []
10 current = root
11 prevVal = -float('inf')
12
13 while stack or current:
14 while current:
15 stack.append(current)
16 current = current.left
17 current = stack.pop()
18 if current.val <= prevVal:
19 return False
20 prevVal = current.val
21 current = current.right
22
23 return TrueThis Python solution uses a list as a stack to conduct iterative in-order traversal. It checks each node's value against the last visited to determine BST validity.