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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public bool IsValidBST(TreeNode root) {
10 return Validate(root, long.MinValue, long.MaxValue);
11 }
12
13 private bool Validate(TreeNode node, long min, long max) {
14 if (node == null) return true;
15 if (node.val <= min || node.val >= max) return false;
16 return Validate(node.left, min, node.val) && Validate(node.right, node.val, max);
17 }
18}The Validate method checks if each subtree is a valid BST by maintaining a dynamic range of minimum and maximum allowable values for nodes.
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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
9 this.val = val;
10 this.left = left;
11 this.right = right;
12 }
13}
14
15public class Solution {
16 public bool IsValidBST(TreeNode root) {
17 Stack<TreeNode> stack = new Stack<TreeNode>();
18 TreeNode current = root;
19 long prevVal = long.MinValue;
20
21 while (stack.Count > 0 || current != null) {
22 while (current != null) {
23 stack.Push(current);
24 current = current.left;
25 }
26 current = stack.Pop();
27 if (current.val <= prevVal) return false;
28 prevVal = current.val;
29 current = current.right;
30 }
31 return true;
32 }
33}The C# solution applies an iterative method using the System.Collections.Generic.Stack class to traverse the tree and maintain the required order property of BST nodes.