Lowest Common Ancestor for a BST

lowestCommAncBST.go

/**
Algorithm

- Start traversing the tree from the root node.
- If both p and q are < root, then continue to left subtree and starting step 1.
- If both p and q are > root, then continue to right subtree and starting step 1.
- If both step 2 and step 3 are not true, we have found the LCA for p and q, and we return it
*/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    
    if(p.Val < root.Val && q.Val < root.Val) {
        return lowestCommonAncestor(root.Left, p, q)   
    }
    
    if(p.Val > root.Val && q.Val > root.Val) {
        return lowestCommonAncestor(root.Right, p, q)   
    }
    
    return root
}