CODEWITHSUNDEEP
pythonpython-3.x
guanyu ma
guanyu ma

Reputation: 15

Calculate paths in binary tree

Hi in this code I tried to calculate the paths in the binary tree(data Structure). But in some case it will give me an error said that "AttributeError: 'int' object has no attribute 'left'" How can I fix this problem? For example in this case 

tree = BTNode(None, BTNode(None,1, 5), BTNode(8))

I will have the attribute error.

class BTNode:
  """A node in a binary tree."""

  def __init__(self: 'BTNode', item: object, 
           left: 'BTNode' =None, right: 'BTNode' =None) -> None:
    """Initialize this node.
    """
    self.item, self.left, self.right = item, left, right

  def __repr__(self):
     return 'BTNode({}, {}, {})'.format(self.item, str(self.left), 
             str(self.right))


 def tree_paths(t: BTNode) -> int:
  '''Return number of paths to get from root of t,
  to all houses, and back to t.

  >>> tree_paths(BTNode(None, BTNode(4), BTNode(5)))
  4
  '''
  ll = 0
  rl = 0
  if t is None:
     return -2
  if t.left is not None and t.left != int:
     ll = tree_paths(t.left) + 2
  if t.right is not None and t.right != int:
     rl = tree_paths(t.right) + 2

  return ll + rl

The error I see is:

Traceback (most recent call last):
  File "<pyshell#11>", line 1, in <module>
    tree_paths(t)
  File "C:\Users\ma\Desktop\CSC148\lab7\trick.py", line 60, in tree_paths
    ll = tree_paths(t.left) + 2
  File "C:\Users\ma\Desktop\CSC148\lab7\trick.py", line 60, in tree_paths
    ll = tree_paths(t.left) + 2
  File "C:\Users\ma\Desktop\CSC148\lab7\trick.py", line 59, in tree_paths
    if t.left is not None and t.left != int:
AttributeError: 'int' object has no attribute 'left'

Upvotes: 0

Views: 61

Answers (1)

Bailey Parker
Bailey Parker

Reputation: 15903

The exception tells you exactly what went wrong. One of your node's lefts is an integer instead of BTNode (which according to your type annotations is what left and right should be).

The problem here is the BTNode(None, 1, 5). This is creating a BTNode with item = None, left = 1 and right = 5. left and right need to be BTNodes. So instead of:

tree = BTNode(None, BTNode(None, 1, 5), BTNode(8))

Try:

tree = BTNode(None, BTNode(None, BTNode(1), BTNode(5)), BTNode(8))

Some ideas on how to prevent this in the future:

Note that type annotations are optional in Python and not enforced by the interpreter. If you want to check if your program is typed soundly, you need to run mypy on your codebase. It will complain for a few reasons:

  1. BTNode(None, 1, 5) - because the 1 and 5 aren't BTNodes
  2. The types of left and right need to be Optional[BTNode] since they can be None (from typing import Optional)

It also may be easier to see this if you constructed the tree using named args:

tree = BTNode(item=None, left=BTNode(item=None, left=1, right=5), right=BTNode(8))

Also look into typing.Generic so that you can leverage the type system more when getting item out of your BTNode (and not having to do unsafe casts).

Upvotes: 1

Related Questions