14

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
Improve this question
4
  • +1 for the correct intuition of your problem. Commented Mar 5, 2013 at 2:39
  • 1
    For future reference, I believe that new bee is spelled newbie, if I'm not mistaken. Commented Mar 5, 2013 at 2:46
  • The intuition is partially correct (calling depth() as a method solves the problem), but somewhat incomplete. The root cause that explains why you can't access the method from inside itself but you can with a regular function is a somewhat involved detail of how scope and class definition works in Python. When you call a regular module-level function, it's "global" scope will be the module it's defined in, which contains this function. However, the scope where methods are defined can be considered to be discarded after the type object created. Commented Mar 5, 2013 at 2:46
  • 1
    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. Commented Mar 5, 2013 at 2:48

4 Answers 4

Reset to default
13 
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)

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

I believe you want to call depth since it is a function :)
Mashing it into one line is a bit unreadable, but this is the right answer.
Wouldn't Node need a __bool__ or __nonzero__ method for the if self.left tests to actually work?
@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.
@Hamish I recoded it in a more readable form also. Thanks for the suggestion
|
4

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
Improve this answer

6 Comments

For clarity I would suggest not using the same name for the method and a local variable in it.
So all nodes have the same depth of 1? Why this?
@Hyperboreus: this is essentially what his code was doing, I didn't check the correctness. Simply gave a more readable pattern :)
@millimoose: fair enough, I'll change it :)
But why would you want to post deliberately wrong code? Both the question and the other answer do add 1 in the recursion.
|
1

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.

Improve this answer

Comments

1

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
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.