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.
1#include <limits.h>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11public:
12 bool validate(TreeNode* node, long min, long max) {
13 if (!node) return true;
14 if (node->val <= min || node->val >= max) return false;
15 return validate(node->left, min, node->val) &&
16 validate(node->right, node->val, max);
17 }
18
19 bool isValidBST(TreeNode* root) {
20 return validate(root, LONG_MIN, LONG_MAX);
21 }
22};The method validate performs a similar function as in C. It checks the current node's validity and calls itself for left and right subtrees with updated constraints.
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.
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 stack = [];
9 let current = root;
10 let prevVal = -Infinity;
11
12 while (stack.length > 0 || current !== null) {
13 while (current !== null) {
14 stack.push(current);
15 current = current.left;
16 }
17 current = stack.pop();
18 if (current.val <= prevVal) return false;
19 prevVal = current.val;
20 current = current.right;
21 }
22 return true;
23};This JavaScript approach leverages arrays to simulate a stack, traversing and checking all nodes in an iterative in-order manner, maintaining the correct order for a BST.