Bottom-up way to solve isBST.


  • 0
    M

    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));
        }
    }
    
    

Log in to reply
 

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