package LeetCode;

public class LeetCode253 {

    /// 235. Lowest Common Ancestor of a Binary Search Tree
    /// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
    /// : O(lgn), n
    /// : O(h), h


    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (p == null || q == null)
            throw new IllegalArgumentException("p or q can not be null.");

        if (root == null)
            return null;

        // p q root
        if (p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);

        // p q root
        if (p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);

        assert p.val == root.val || q.val == root.val
                || (root.val - p.val) * (root.val - q.val) < 0;

        // rootroot
        return root;
    }

}