Problem:
Given a binary tree (BST), determine if it is valid.
A BST satisfy the following rule for any node:
the left subtree's node values are all smaller than the current node value, the right subtree's node values are all bigger than the current node value.
For Example the following BST is invalid, because the right subtree has a node value 3 that is smaller than the root node value 8
8
/ \
1 3
In the following example, the BST is valid
5
/ \
1 8
/ \
6 9
Solution:
We can solve this with recursive. One pitfall is to check root.left.value < root.value < root.right.value. That check is not enough. The following BST is invalid, but at each node, the root.left.value < root.value < root.right.value holds. What we want to check is each node fall into a value range of (llimit, ulimit)
5
/ \
1 6
/ \
4 9
import java.util.*;
class Solution {
public static void main(String[] args) {
Node root = new Node(5, new Node(1, null, null), new Node(8, new Node(6, null, null), new Node(9, null, null)));
System.out.println(isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
root = new Node(8, new Node(1, null, null), new Node(3, null, null));
System.out.println(isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
root = new Node(5, null, null);
System.out.println(isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
private static boolean isValid(Node root, int llimit, int ulimit) {
if(root == null) return true;
if(root.value < llimit || root.value > ulimit) return false;
return isValid(root.left, llimit, root.value)
&& isValid(root.right, root.value, ulimit);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
The time complexity is O(N) because we have to visit all the nodes, the space complexity is O(H), where H is the tree's height.
