235. Lowest Common Ancestor of a Binary Search Tree

# 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':
        """  tc O(N)  sc O(H)
        assuming all nodes unique and both q,p exist in the tree 
        (1)if root == p  (2) q == root (3) between  [p,q] 
        main idea:  use st doing inorder traversal if root < both p, q, root go to the right ; if root > both p,q root go to left;
        terminate until root meet one of the three cases above 
        """
        
        if root.val>max(p.val, q.val):
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val<min(p.val, q.val):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root
        # if root.val == p.val or root.val == q.val:
        #     return root 
        # elif (q.val > root.val > p.val) or (p.val > root.val > q.val):
        #     return root 
            

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        tc O(H)  sc O(1)
        """
        while root:
            if p.val <root.val  and  q.val < root.val :
                root = root.left
            elif p.val > root.val  and  q.val > root.val :
                root = root.right
            else:
                return root