https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Leetcode: 235. Lowest Common Ancestor of a Binary Search Tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // p,q are both under root.Left
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }
    // p,q are both under root.Right
    if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }
    // p,q are split, BINGO!
    return root
}

// At first I solved this forgetting that the problem was on a BINARY tree, so the 
// solution is definitely more complicated than it needs to be

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    var helper func(node *TreeNode) (*TreeNode, bool, bool)
    helper = func(node *TreeNode) (*TreeNode, bool, bool) {
        if node == nil {
            return nil, false, false
        }
        la, lp, lq := helper(node.Left)
        if la != nil {
            return la, true, true
        }
        ra, rp, rq := helper(node.Right)
        if ra != nil {
            return ra, true, true
        }
        cp := lp || rp || node.Val == p.Val
        cq := lq || rq || node.Val == q.Val
        if cp && cq {
            return node, true, true
        }
        return nil, cp, cq
    }
    node, _, _ := helper(root)
    return node
}