LeetCode 98 - Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/description/

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

1. follow up: preorder和postorder⾏不⾏
2. follow-up: validate balanced tree 和 validate balanced BST
3. Postorder 需要维护⼀一个MinMax区间
4. balanced 左右子树⾼度相差最⼤大为1
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/098_Validate_Binary_Search_Tree.java

// new inorder
    public boolean isValidBST(TreeNode root) {
        return helper(root);
    }
    
    TreeNode prev = null;
    
    private boolean helper(TreeNode root) {
        if (root == null) return true;
        if (!helper(root.left)) return false;
        if (prev != null && prev.val >= root.val) return false;
        prev = root;
        return helper(root.right);
    }

// new preorder
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean helper(TreeNode root, long min, long max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return helper(root.left, min, root.val) & helper(root.right, root.val, max);
    }

X.

Basically what I am doing is recursively iterating over the tree while defining interval <minVal, maxVal> for each node which value must fit in.

https://discuss.leetcode.com/topic/7179/my-simple-java-solution-in-3-lines

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }

Use Optional for edge cases with MIN_VALUE and MAX_VALUE.

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Optional.empty(), Optional.empty());
    }
    
    private boolean isValidBST(TreeNode node, Optional<Integer> min, Optional<Integer> max) {
        if (node == null) {
            return true;
        }
        if ((min.isPresent() && node.val <= min.get()) || (max.isPresent() && node.val >= max.get())) {
            return false;
        }
        Optional val = Optional.of(node.val);
        return isValidBST(node.left, min, val) && isValidBST(node.right, val, max);
    }

https://discuss.leetcode.com/topic/17340/another-passed-java-solution/

    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    
    boolean helper(TreeNode root, Integer min, Integer max) {
        if (root == null)
            return true;
        
        if ((min != null && root.val <= min) || (max != null && root.val >= max))
            return false;
        
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

X. https://www.jiuzhang.com/solutions/validate-binary-search-tree/

    private int lastVal = Integer.MIN_VALUE;
    private boolean firstNode = true;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (!firstNode && lastVal >= root.val) {
            return false;
        }
        firstNode = false;
        lastVal = root.val;
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;
    }

X. Iterative Stack

https://discuss.leetcode.com/topic/46016/learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-java-solution

Question : Binary Tree Inorder Traversal

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
        
    }
    return list;
}

Now, we can use this structure to find the Kth smallest element in BST.

Question : Kth Smallest Element in a BST

 public int kthSmallest(TreeNode root, int k) {
     Stack<TreeNode> stack = new Stack<>();
     while(root != null || !stack.isEmpty()) {
         while(root != null) {
             stack.push(root);    
             root = root.left;   
         } 
         root = stack.pop();
         if(--k == 0) break;
         root = root.right;
     }
     return root.val;
 }

We can also use this structure to solve BST validation question.

Question : Validate Binary Search Tree

public boolean isValidBST(TreeNode root) {
   if (root == null) return true;
   Stack<TreeNode> stack = new Stack<>();
   TreeNode pre = null;
   while (root != null || !stack.isEmpty()) {
      while (root != null) {
         stack.push(root);
         root = root.left;
      }
      root = stack.pop();
      if(pre != null && root.val <= pre.val) return false;
      pre = root;
      root = root.right;
   }
   return true;
}

https://discuss.leetcode.com/topic/7526/my-java-inorder-iteration-solution

public boolean isValidBST (TreeNode root){
     Stack<TreeNode> stack = new Stack<TreeNode> ();
     TreeNode cur = root ;
     TreeNode pre = null ;     
     while (!stack.isEmpty() || cur != null) {      
      if (cur != null) {
       stack.push(cur);
       cur = cur.left ;
      } else {       
       TreeNode p = stack.pop() ;
       if (pre != null && p.val <= pre.val) {        
        return false ;
       }       
       pre = p ;        
       cur = p.right ;
      }
     }
     return true ; 
    }

X.  Post-order travsere 
https://www.jiuzhang.com/solutions/validate-binary-search-tree/

class ResultType {
    boolean is_bst;
    int maxValue, minValue;
    
    ResultType(boolean is_bst, int maxValue, int minValue) {
        this.is_bst = is_bst;
        this.maxValue = maxValue;
        this.minValue = minValue;
    }
}
    public boolean isValidBST(TreeNode root) {
        ResultType r = validateHelper(root);
        return r.is_bst;
    }
    
    private ResultType validateHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(true, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        
        ResultType left = validateHelper(root.left);
        ResultType right = validateHelper(root.right);
        
        if (!left.is_bst || !right.is_bst) {
            // if is_bst is false then minValue and maxValue are useless
            return new ResultType(false, 0, 0);
        }
        
        if (root.left != null && left.maxValue >= root.val || 
              root.right != null && right.minValue <= root.val) {
            return new ResultType(false, 0, 0);
        }
        
        return new ResultType(true,
                              Math.max(root.val, right.maxValue),
                              Math.min(root.val, left.minValue));
    }

Write a function isBST(BinaryTree *node) to verify if a given binary tree is a Binary Search Tree (BST) or not.

bool isBSTHelper(BinaryTree *p, int low, int high) {

  if (!p) return true;

  if (low < p->data && p->data < high)

    return isBSTHelper(p->left, low, p->data) &&

           isBSTHelper(p->right, p->data, high);

  else

    return false;

}

bool isBST(BinaryTree *root) {

  // INT_MIN and INT_MAX are defined in C++'s <climits> library

  return isBSTHelper(root, INT_MIN, INT_MAX);  

}

Inorder Traversal:
Another solution is to do an in-order traversal of the binary tree, and verify that the previous value (can be passed into the recursive function as reference) is less than the current value. This works because when you do an in-order traversal on a BST, the elements must be strictly in increasing order. This method also runs in O(N) time and O(1) space.

bool isBSTInOrderHelper(BinaryTree *p, int& prev) {

  if (!p) return true;

  if (isBSTInOrderHelper(p->left, prev)) {

    if (p->data > prev) {

      prev = p->data;

      return isBSTInOrderHelper(p->right, prev);

    } else {

      return false;

    }

  }

  else {

    return false;

  }

}

http://www.cnblogs.com/yuzhangcmu/p/4177047.html
http://www.lifeincode.net/programming/leetcode-validate-binary-search-tree-java/
Doing a in-order traverse on a BST, the output will be a increasing sequence.

    public boolean isValidBST(TreeNode root) {

        return inorderTraverse(root);

    }

    TreeNode prev = null;

    public boolean inorderTraverse(TreeNode root) {

        if (root == null)

            return true;

        if (!inorderTraverse(root.left))

            return false;

        if (prev != null) {

            if (root.val <= prev.val)

                return false;

        }

        prev = root;

        if (!inorderTraverse(root.right))

            return false;

        return true;

    }

http://blog.csdn.net/linhuanmars/article/details/23810735

public boolean isValidBST(TreeNode root) {
    ArrayList<Integer> pre = new ArrayList<Integer>();
    pre.add(null);
    return helper(root, pre);
}
private boolean helper(TreeNode root, ArrayList<Integer> pre)
{
    if(root == null)
        return true;
    boolean left = helper(root.left,pre);
    if(pre.get(0)!=null && root.val<=pre.get(0))
        return false;
    pre.set(0,root.val);
    return left && helper(root.right,pre);
}

In-order iterative traversal:
http://www.cnblogs.com/yuzhangcmu/p/4177047.html

1 public boolean isValidBST1(TreeNode root) {
 2         // Just use the inOrder traversal to solve the problem.
 3         if (root == null) {
 4             return true;
 5         }
 7         Stack<TreeNode> s = new Stack<TreeNode>();
 8         TreeNode cur = root;
10         TreeNode pre = null;
12         while(true) {
13             // Push all the left node into the stack.
14             while (cur != null) {
15                 s.push(cur);
16                 cur = cur.left;
17             }
18             
19             if (s.isEmpty()) {
20                 break;
21             }
23             // No left node, just deal with the current node.
24             cur = s.pop();
26             if (pre != null && pre.val >= cur.val) {
27                 return false;
28             }
30             pre = cur;
32             // Go to the right node.
33             cur = cur.right;
34         }
36         return true;
37     }

http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
METHOD 2 (Correct but not efficient)
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.

int isBST(struct node* node)

{

  if (node == NULL)

    return(true);

     

  /* false if the max of the left is > than us */

  if (node->left!=NULL && maxValue(node->left) > node->data)

    return(false);

     

  /* false if the min of the right is <= than us */

  if (node->right!=NULL && minValue(node->right) < node->data)

    return(false);

   

  /* false if, recursively, the left or right is not a BST */

  if (!isBST(node->left) || !isBST(node->right))

    return(false);

     

  /* passing all that, it's a BST */

  return(true);

}

X. https://leetcode.com/articles/validate-binary-search-tree/

  public boolean isBSTHelper(TreeNode node, Integer lower_limit, Integer upper_limit) {

    if ((lower_limit != null) && (node.val <= lower_limit))

      return false;

    if ((upper_limit != null) && (upper_limit <= node.val))

      return false;

    boolean left = node.left != null ? isBSTHelper(node.left, lower_limit, node.val) : true;

    if (left) {

      boolean right = node.right != null ? isBSTHelper(node.right, node.val, upper_limit) : true;

      return right;

    } else

      return false;

  }

  public boolean isValidBST(TreeNode root) {

    if (root == null)

      return true;

    return isBSTHelper(root, null, null);

  }

X.
https://algorithms.tutorialhorizon.com/determine-whether-given-binary-tree-is-binary-search-treebst-or-not/

Method 2: The Max/Min Solution :

When we talk about binary search tree we talk about one property i.e leftChild.data <=root.data<rightChild, but checking alone this property at every node is not gonna work out, want to know why, see this example

Invalid BST

Now in the above example you can see that when you validate the Node 40, 10<=40<50 so it will return true nad when you validate the Node 30, 5<=30<40, will return true but as you can see that this tree is not BST since 10 is smaller than 30 so it should be on the left of the 30. Actually all the nodes less than 30 should be on the left and all the nodes greater than 30 should be on the right.

How would you achieve that???

Your root value can have any value between -∞ to + ∞. When you validate the right child of 30, it can take any value between 30 and + ∞. When you validate the left child of 30, it can take any value between – ∞ and 30. likewsie when you validate the left child of 40, it can take any value between 30 and 40.

So the idea is Pass the minimum and maximum values between which the node’s value must lie.

 // method 1: do inOrder and check if it is in ascending order
 // doesnt work in case of duplicates
 public boolean isBST1(Node root) {
  if (root != null) {
   if (!isBST1(root.left))
    return false;
   if (prevNode != null && prevNode.data >= root.data) {
    return false;
   }
   prevNode = root;
   return isBST1(root.right);
  }
  return true;
 }

 // //method 2
 // The max-Min solution
 public boolean isBST2(Node root, int min, int max) {
  if (root != null) {
   if (root.data > max || root.data < min) {
    return false;
   }
   return isBST2(root.left, min, root.data)
     && isBST2(root.right, root.data, max);
  } else {
   return true;
  }
 }