Find LCA of p = 2 and q = 8 in the BST rooted at 6.
At node 6: p = 2 < 6 and q = 8 > 6. Split! Node 6 is the LCA.
Find LCA of p = 2 and q = 4:
At node 6: both 2 and 4 < 6. Go left.
At node 2: p = 2 equals current. q = 4 > 2. Split! Node 2 is the LCA.
Find LCA of p = 0 and q = 4:
At node 6: both < 6. Go left.
At node 2: p = 0 < 2 and q = 4 > 2. Split! Node 2 is the LCA.
Single path from root to LCA. time where is tree height. space with iteration (or with recursion).