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

score 1 · Answer 1 · answered May 19 '18 at 15:04

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.

Yilmaz, the progression makes sense but what doesn't is how the returned value of `root` is `4` and not `6` if the `root` value is not explicitly updated. — heretoinfinity, May 19 '18 at 16:11
`root` is not kept constant. As you proceed to new function, your new root is either `root.left` or `root.right`. You can see it by adding a `print("root: " + root)` on the first line of function. — Ali Yılmaz, May 20 '18 at 00:09

sheldonzy · Accepted Answer · 2018-05-19T16:19:17.510

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.

edited May 19 '18 at 16:19

answered May 19 '18 at 15:15

sheldonzy

5,505
9
48
86

if I am passing references, how is it that `root` is not `6` (if the root isn't changed) but `4`? I didn't think the `root` was changed so I was expecting `6` but the value returned is `4`. – heretoinfinity May 19 '18 at 16:09
the value of each individual object doesn't change, but when you pass `root.left` to the function as an argument, you pass a reference to `root.left`, then the `root` in your new function will be the `root.left` of your previous root. the `root` in each function call will be different. – sheldonzy May 19 '18 at 16:17
1

I think I get it. You keep calling the function when the root value isn't between the values of `p` and `q`. When you get to the situation where it is, you return the root value of that specific function call [since you skipped the `if` statements]. The returned value gets relayed back to the main function call that initiated the recursion and because this first main call has a `return` statement, it returns that value and doesn't get to the last `return root` statement so the `root` remains the same [`6`] but the value returned is of the node that satisfied the condition i.e. `4`. – heretoinfinity May 19 '18 at 16:45

Python: recursion in finding common ancestor in binary search tree

2 Answers2