Lowest Common Ancestor: BST*

First Thoughts: (by this time I was not aware that binary search trees BST are "search" trees, meaning when nodes are added, nodes that are smaller than current node are placed on the left, and nodes that are greater than current node are placed on the right)

Solution:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val<root.val && q.val<root.val) return lowestCommonAncestor(root.left, p, q);
        else if (p.val>root.val && q.val>root.val) return lowestCommonAncestor(root.right, p, q);
        else return root;
    }
}

Catch Point

1. If the two target nodes (p and q) are on the same side (meaning both onto the left or right side of the node), then we can "remove one layer" and input the modified version of the function -> use of recursion

2. The lowest common ancestor happens only when the two target nodes are placed on each side of the node (including the case where the node itself is the target node)