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


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts