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#include <stdbool.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10bool validate(struct TreeNode* node, long min, long max) {
11 if (node == NULL) return true;
12 if (node->val <= min || node->val >= max) return false;
13 return validate(node->left, min, node->val) &&
14 validate(node->right, node->val, max);
15}
16
17bool isValidBST(struct TreeNode* root) {
18 return validate(root, LONG_MIN, LONG_MAX);
19}The validate function checks if the current node's value is within the valid range dictated by min and max. It recursively checks the left subtree with an updated max and the right subtree with an updated min.
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 <stdbool.h>
2#include <stdlib.h>
3#include <limits.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11struct Stack {
12 struct TreeNode **data;
13 int top;
14};
15
16void push(struct Stack *stack, struct TreeNode *node) {
17 stack->data[++stack->top] = node;
18}
19
20struct TreeNode *pop(struct Stack *stack) {
21 return stack->data[stack->top--];
22}
23
24bool isEmpty(struct Stack *stack) {
25 return stack->top == -1;
26}
27
28bool isValidBST(struct TreeNode* root) {
29 struct Stack stack = { .data = malloc(10000 * sizeof(struct TreeNode *)), .top = -1 };
30 struct TreeNode *current = root;
31 long prevVal = LONG_MIN;
32
33 while (!isEmpty(&stack) || current != NULL) {
34 while (current != NULL) {
35 push(&stack, current);
36 current = current->left;
37 }
38 current = pop(&stack);
39 if (current->val <= prevVal)
40 return false;
41 prevVal = current->val;
42 current = current->right;
43 }
44 free(stack.data);
45 return true;
46}This solution uses a manual stack (implemented as a struct in C) to perform in-order traversal. We keep track of the previous node's value to ensure all nodes are in increasing order.