Python: recursion in finding common ancestor in binary search tree

Question

I have been looking at the pasted code below in the Discuss tab of Leetcode and I feel I don't fully understand recursion. The question is about finding the common ancestor of 2 nodes in a binary search tree.

def lowestCommonAncestor(self, root, p, q):
    if p.val < root.val > q.val:
        return self.lowestCommonAncestor(root.left, p, q)
    if p.val > root.val < q.val:
        return self.lowestCommonAncestor(root.right, p, q)
    return root

Could explain to me how root is changed such that it gives the answer without its value being updated? I see root being passed into the main function (an argument like p and q) but the recursive calls only take root.left and root.right.

Could you clarify the recursion with an explanation of finding the common ancestor of 3 and 5?

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

The Stackoverflow accepted answer here uses recursion but doesn't answer my question.

Where I found the code: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/discuss/64963/3-lines-with-O(1)-space-1-Liners-Alternatives

Answer 1

You start at the root of the tree, and p and q are the nodes you want to get their common ancestor.

For you example, when p is the node 3, and q is the node 5. The root is 6.

So p.val < root.val > q.val will hold, and now you will call self.lowestCommonAncestor(root.left, p, q). You are just moving references of objects between functions.

Now your root will be 2 (the left of root), and p and q are the same. Now, if p.val > root.val < q.val will hold, because 3 > 2 and 5 > 2, so we will call self.lowestCommonAncestor(root.right, p, q). When we put the argument root.right, this is just a reference to a different object. Just to clarify, this does not change the value of any object, but it changes the value of root within the scope of the current function.

Now your root will be 4, and none of the conditions will hold, so you will return 4 as your common ancestor.

Answer 2

Those if statements check if q and p are on the same side with respect to root.

First if's meaning: both p and q are smaller than root, so they're on the left side. So, root is not their lowestCommonAncestor. For example, 3 and 5 in your example tree. They fall into this case. They are both lower than 6, so their common ancestor is somewhere within the left part of main tree. Proceed to next step with lowestCommonAncestor(root.left, p, q).

Second: Same as first, except, they're now on the right side. They are both greater than root, so they must have a lowestCommonAncestor somewhere in root.right.

This function proceeds until, there is such a case that, p and q are not on the same side anymore. In this case, root is the lowestCommonAncestor.