###### tags: `Week_2`, `Binary Search Tree`

# Binary Search Tree

## 98. [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)

harry:
https://github.com/harryuan65/Grindy-Viking/blob/master/Medium/98.validate-binary-search-tree/images/solution.png

def is_valid_bst(root)
  validate(root, -Float::INFINITY, Float::INFINITY)
end

def validate(node, min, max)
  val = node.val
  left = node.left
  right = node.right

  self_valid = val.between?(min, max)
  return self_valid if left.nil? && right.nil?


  self_valid &&= left.val < val if left
  self_valid &&= right.val > val if right

  min_valid = val > min
  min_valid &&= left.val > min if left
  min_valid &&= right.val > min if right

  max_valid = val < max
  max_valid &&= left.val < max  if left
  max_valid &&= right.val < max if right
  return false unless min_valid && max_valid

  children_valid = true
  children_valid &&= validate(left,  min, val) if left
  children_valid &&= validate(right, val, max) if right
  min_valid && max_valid && self_valid && children_valid
end

harry(2)
https://github.com/harryuan65/Grindy-Viking/blob/master/Medium/98.validate-binary-search-tree/images/solution2.png

def is_valid_bst(root)
  validate(root, -Float::INFINITY, Float::INFINITY)
end

def validate(node, min, max)
  val = node.val
  valid = val > min && val < max

  valid &&= validate(node.left, min, node.val) if node.left
  valid &&= validate(node.right, node.val, max) if node.right
  valid
end

sam:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        inorder_list = []
        
        def inorder(root):
            if root is None:
                return
            inorder(root.left)
            inorder_list.append(root.val)
            inorder(root.right)
        
        inorder(root)
        if len(inorder_list) == 1:
            return True
        
        for i in range(1, len(inorder_list)):
            if inorder_list[i] <= inorder_list[i-1]:
                return False

        return True

hazel:

Beny

public class Solution {
    public bool IsValidBST(TreeNode root) {
        if(root == null){
            return false;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();         
        TreeNode pre = null;
        while(root != null || stack.Count > 0){            
            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;       
    }
}

## 235. [Lowest Common Ancestor of a Binary](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)

harry:

sam:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        p_val = p.val
        q_val = q.val
        
        while root:
            if root.val > p_val and root.val > q_val:
                root = root.left
            elif root.val < p_val and root.val < q_val:
                root = root.right
            else:
                return root
        
        

hazel:

Beny

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode pre = root;     
        int big,small; 
        if(p.val > q.val){            
            big = p.val;
            small = q.val;
        }else{
            big = q.val;
            small = p.val;
        }
       while(pre != null){
            if(pre.val >= small && pre.val <= big){
                return pre;
            }else if(pre.val <= small){
                pre = pre.right;
            }else if(pre.val >= big){
                pre = pre.left;
            }
        }  
        return p;
    }
}