# Bottom-up way to solve isBST.

• Almost all of the current solutions are top-down way to solve this problem. This post will give one solution by using bottom-up way. Idea came from the solution from Largest BST subtree.

Bottom-up way can gives us the subtree isBST or not. For each child node, it needs to submit three variable to its parent: 1. it’s a BST or not; 2. lower value in its subtree; 3. upper value in its subtree.

BST must satisfy that: left.upper < root.val < right.lower.

For the null node, we can return 1. isBST = true; 2. lower = Long.MAX_VALUE; 3. upper = Long.MIN_VALUE.

``````public class Solution {
static class Element {
boolean isBST;
long lower;
long upper;

Element(boolean isBST, long l, long u) {
this.isBST = isBST;
this.lower = l;
this.upper = u;
}
}

public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Element res = helper(root);
return res.isBST;
}

private Element helper(TreeNode root) {
if (root == null) {
return new Element(true, Long.MAX_VALUE, Long.MIN_VALUE);
}
Element left = helper(root.left);
Element right = helper(root.right);

if (!left.isBST || !right.isBST || root.val <= left.upper || root.val >= right.lower) {
return new Element(false, 0, 0);
}

return new Element(true, Math.min(left.lower, root.val), Math.max(right.upper, root.val));
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.