calculating depth of a binary tree in Python

Question

I am new to programming and am trying to calculate the depth of a binary tree in Python . I believe that my error is because depth is a method of the Node class and not a regular function. I am trying to learn OOP and was hoping to use a method. This might be a newbie error... Here is my code:

class Node:

    def __init__(self, item, left=None, right=None):
        """(Node, object, Node, Node) -> NoneType
        Initialize this node to store item and have children left and right.
        """
        self.item = item
        self.left = left
        self.right = right

    def depth(self):
        if self.left == None and self.right == None:
            return 1

        return max(depth(self.left), depth(self.right)) + 1

i receive this error:

>>>b = Node(100)

>>>b.depth()

1 

>>>a = Node(1, Node(2), Node(3))

>>>a.depth()

Traceback (most recent call last):
  File "C:\Program Files\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 1, in <module>
    # Used internally for debug sandbox under external interpreter
  File "C:\Program Files\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 15, in depth
builtins.NameError: global name 'depth' is not defined

Solution 1

def depth(self):
    if self.left == None and self.right == None:
        return 1

    return max(depth(self.left), depth(self.right)) + 1

should be

def depth(self):
    return max(self.left.depth() if self.left else 0, self.right.depth() if self.right else 0) + 1

A more readable version:

def depth(self):
    left_depth = self.left.depth() if self.left else 0
    right_depth = self.right.depth() if self.right else 0
    return max(left_depth, right_depth) + 1

The issue is that there is no function depth. It's a method of the Node object, so you would need to call it from the object itself (left and right). I shortened the code to self.left.depth() if self.left else 0 and self.right.depth() if self.right else 0 in order to remove the checks you previously have (they're implicit now) since I believe it is entirely possible that the left is None while the right is a Node or vice versa, which would cause the original code to throw an AttributeError since None does not have a method depth.

Edit

In response to the question about the <something> if <some condition> else <otherwise> block:

The line gives <something> if <some condition> is true-y (treated as true), and <otherwise> if <some condition> is false-y (treated as false)

Solution 2

For clarity I would suggest writing your depth method like this:

def depth(self):
    current_depth = 0

    if self.left:
        current_depth = max(current_depth, self.left.depth())

    if self.right:
        current_depth = max(current_depth, self.right.depth())

    return current_depth + 1

Solution 3

The error is coming from this line:

return max(depth(self.left), depth(self.right)) + 1

You're using depth as a function and trying to apply it to the left and right nodes. Because the left and right nodes are also nodes, they have the depth method.

You should be calling the depth method like this:

return max(self.left.depth(), self.right.depth()) + 1

The self parameter is implicitly passed to the depth method, but using it with the dot operator tells Python that this method belongs to a Node instance, and it is not some other function not bound to an object.

Solution 4

You've got four cases to consider:

1. Both subtrees are empty.
2. The left subtree alone is empty.
3. The right subtree alone is empty.
4. Neither subtree is empty.

You've covered cases 1 and 4, but missed 2 and 3. The fix:

# Return height of tree rooted at this node.
def depth(self):
    if self.left == None and self.right == None:
        return 1
    elif self.left == None:
        return self.right.depth() + 1
    elif self.right == None:
        return self.left.depth() + 1
    else:
        return max(self.left.depth(), self.right.depth()) + 1

View more solutions

Comments

[Snakes and Coffee]

For future reference, I believe that new bee is spelled newbie, if I'm not mistaken.

[abarnert]

As a side note, you should always use self.left is None, not self.left == None, as PEP 8 says. This protects you from badly-designed classes, and adds a performance boost, but the real reason is that "is None" stands out as the one Pythonic way to do it, and makes your code more readable to experienced Python coders.

[Wolph]

I believe you want to call depth since it is a function :)

[Hamish]

Mashing it into one line is a bit unreadable, but this is the right answer.

[Montre]

For clarity I would suggest not using the same name for the method and a local variable in it.

[Marius]

Wouldn't Node need a __bool__ or __nonzero__ method for the if self.left tests to actually work?

[abarnert]

@Marius: No, the default is to return the object itself, which is true in boolean contexts, and therefore self.left is a valid test for self.left is not None.

[Snakes and Coffee]

@Hamish I recoded it in a more readable form also. Thanks for the suggestion

[abarnert]

PS, @SnakesandCoffee: Nice explanation for why you can't just do if self.left is None and self.right is None. If the OP wanted to leave the structure as-is, he'd also have to write something like elif self.left is None: return self.right.depth()+1 and elif self.right is None: return self.left.depth()+1. So, I think your version is more readable.

[Hyperboreus]

So all nodes have the same depth of 1? Why this?

[user2133075]

@Snakes and Coffee: Thank you very much for your help and detailed explanation! What does this line of code mean: if self.left else 0 - i have never seen an if and an else on the same line. Sorry for the newbie question...

[Snakes and Coffee]

@user2133075 if you found this answer to be the right answer, please click the green check mark next to the votes (it gives me 15 rep and you 2 I believe)

[Snakes and Coffee]

@user2133075 I added the explanation for the a if b else c lines

[Wolph]

@Hyperboreus: this is essentially what his code was doing, I didn't check the correctness. Simply gave a more readable pattern :)

[Wolph]

@millimoose: fair enough, I'll change it :)

[Hyperboreus]

But why would you want to post deliberately wrong code? Both the question and the other answer do add 1 in the recursion.

[Wolph]

The question was modified, my code reflects a working version of the original code. I did not check it for correctness