Potential bug in python implementation of Problem 9.4

[deveshks]

The definition of depth of a node n in the book states:

"The depth of a node n is the number of nodes on the search path from the root to n, not including n itself."

But if you look at the implementation of get_depth, we are also counting the node while performing the traversal from the node to the root.

The problem lies in the while condition at

EPIJudge/epi_judge_python_solutions/lowest_common_ancestor_with_parent.py

Line 12 in 1e03a0c

while node:

which will only break the while loop when node is None, which will happen once node equals parent of root, which is None

Instead the condition should be changed to "while node.parent" which will make sure we break the while when we hit root, and the result will confer to the definition of depth as prescribed in the book

To expand on that further, here is a sample run of get_depth of current code along with get_depth_fixed which adds my suggested fix

class TreeNode:

    def __init__(self, val=None, left=None, right=None):

        self.val = val
        self.left = left
        self.right = right
        self.parent = None

root = TreeNode(1)
root.left = TreeNode(2)
root.left.parent = root
root.right = TreeNode(3)
root.right.parent = root
root.left.left = TreeNode(4)
root.left.left.parent = root.left
root.left.right = TreeNode(5)
root.left.right.parent = root.left
root.right.left = TreeNode(6)
root.right.left.parent = root.right
root.right.right = TreeNode(7)

    def get_depth(node):
        
        depth = 0
        while node:

            depth += 1
            node = node.parent
            
        return depth

     def get_depth_fixed(node):
        
        depth = 0
        while node.parent:

            depth += 1
            node = node.parent
            
        return depth

print(get_depth(root.left)) #Will output 2
print(get_depth(root.left.left)) #Will output 3

print(get_depth_fixed(root.left)) #Will output 1
print(get_depth_fixed(root.left.left)) #Will output 2

[tsunghsienlee]

Hi @deveshks ,

Very sharp eyes, and you are right on this. If you check our C++ and Java implementations, you shall notice that we take care of this but the Python implementation is definitely missing this.

This fix will be pushed in the next release, and really appreciate for your report!

[deveshks]

You are correct, both the C++ implementation
https://github.com/adnanaziz/EPIJudge/blob/master/epi_judge_cpp_solutions/lowest_common_ancestor_with_parent.cc#L37

and the Java implementation
https://github.com/adnanaziz/EPIJudge/blob/master/epi_judge_java_solutions/epi/LowestCommonAncestorWithParent.java#L37

take care of this, and not the Python implementation, Also even the book text contains the same mistake and would need to be fixed.

I would love to create a pull request and contribute the proposed fix in the code, if I am allowed to.

I am currently reading the Python version of the book and finding the questions very helpful, and would love to give back my contribution in the form of a pull request

[tsunghsienlee]

Hi @deveshks ,

Just to be clear, you said

Also even the book text contains the same mistake and would need to be fixed.

Could you point out what exactly the text in the book is wrong such that we could fix that?

It is good to hear that you like the questions in the book, and please keep up the good work on reporting whatever you feel wrong.

[deveshks]

I meant to say that the code provided in the book "Elements of Programming Interviews in Python" for Question 9.4 contains the same issue as the code in the Judge which I pointed out. It's on page 118

Also let me know if I can open a PR to fix this problem with python code.

I also plan to go through the implementations of other python implementation of the code and find out other potential issues

[tsunghsienlee]

I see, thanks for pointing that out. The book actually excerpt the program and fits into there. So as long as the code is fixed, eventually the physical book will be fine.

Originally I was thinking what you referred is the text description part of the book is buggy.

[deveshks]

Hi @tsunghsienlee

I was referring to both the code present in this repo as well as code in the book.

Is there a document which I can follow to create a PR and fix this issue?

[tsunghsienlee]

Hi @deveshks ,

Our book actually has a program to extract the code snippet from repo and insert that into the book. Therefore, they are pointing to same thing.

Right now we don't have document to create PR but we are planning to have one. If you want, just submit one by your own and we will merge that into our repo.

[deveshks]

Hi @tsunghsienlee
Thanks for the response. I assume I can use the dev branch for the PR, since that seems to be the current one and is 15 commits ahead of the master?

[tsunghsienlee]

Hi @deveshks ,

I would suggest you list the problem you discovered to us and make PR if you want. Because the uniqueness structure of the book and development practice, we could not upstream the PR change you made to the book. So we currently only manually merge those changes you guys submit into our private repository.

So if you see commits are behind publicly, it does not mean the internal development is behind.

[deveshks]

Hi @tsunghsienlee

So If I understand correctly, I can choose either the dev or master branch, and make the PR, since you will manually merge the changes from either of the branch?

[tsunghsienlee]

I think the way "merge" is we just manually implement the change you made in the private repository and then when it release, it will be shown in the public repository. Basically whatever you did will not merge in fact, it is more like a demo to us how we could implement that in private repo. So that is the reason I said you could make PR or not, as we have to reimplement that again.

[deveshks]

Got it, I just wanted to make sure I was listed as a committer in the commit log of this repo, hence my questions.

But seems like what you explained to me, that won't be the case since you will manually implement that change and release it here.

[tsunghsienlee]

Yeah, you are right. I feel bad that the commit log for people contribute to open source repository get this as some sort of recognization.

In the open source repository which contains private internal resources, it usually have a bot to auto-push commits back-and-forth keep the public and private side stay at sync so both could work together. However, we don't have this bot, and we have some not-fully developed ideas that we could not share due to other concerns. Therefore, the only thing we could do is to manually merge those users feedbacks by ourselves.

I know this is not ideal, but we authors do really appreciate for every input you guys provide; hope this explains your concerns as I try my best to be transparent as much as I can.

[deveshks]

Thanks for the explanation again and being transparent. I will create a PR and make a commit regardless to help you guys out when you manually merge it to your private repo

[metopa]

Hi @deveshks, feel free to submit the PR. I'll make sure you will be listed as a contributor. Use the dev branch, please.

[deveshks]

Thanks @metopa I have created a PR for the same

[deveshks]

Thanks @metopa for handling the PR and merging the commit. If possible, can you list me as a contributor as you mentioned in a previous comment?

[metopa]

@deveshks GitHub does this automatically as soon as the commit is merged to master