Debug Python: Binary Search Tree (Objects bug)

Question

So I got a small bug in this program but I really couldn't figure out how to fix it and I would be very appreciated it if someone could help me point out where it is. So basically, the first function converts a sorted array to a balanced binary search tree and the second function returns the height of the tree from a given node. When I compiled the program, I got an error like this:

I tried to print out the "aNode" object to test and I was surprise to find that at first it pointed to a Node object, but then pointed to a Tree object(?), which I was really confused and really don't know how to debug this. Thank you very much for any help.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lChild = None
        self.rChild = None

class Tree(object):
    def __init__(self):
        self.root = None
    # create a balanced binary search tree from a sorted list
    def create_tree (self, a_list):
       if (len(a_list) <= 0): return None
       mid = (len(a_list))//2 # find the mid value of the sorted array & make it root
       self.root = Node(a_list[mid])
       self.root.lChild = self.create_tree(a_list[:mid])
       self.root.rChild = self.create_tree(a_list[mid+1:])
       return self

    def get_height (self, aNode):
       if (aNode == None):
          return -1
       else:
          print(aNode) # I DID MY TEST HERE WHERE IT FIRST PRINT "NODE OBJECT", BUT PRINT "TREE OBJECT" LATER AND CAUSE THE PROGRAM TO FAIL
          rHeight = self.get_height(aNode.rChild)
          lHeight = self.get_height(aNode.lChild)
          return (1+rHeight) if rHeight > lHeight else (1+lHeight)

def main():
    new_tree = Tree().create_tree([1,9,11,17])
    new_tree.get_height(new_tree.root)
 main()

Thank you very much!

The "return self" in create_tree function returns a Tree object. During the recursion calls of create_tree, The Tree object gets assigned to your nodes as lChild or rChild. you might want to fix this — Nithin
– Nithin, Commented Apr 27, 2019 at 2:49

Andrew L · Accepted Answer · 2019-04-27 02:43:53Z

1

The problem is you are overriding self.root with a new node each time. So each level down within the recursive calls, you are resetting the Tree object's self.root with a new empty node.

Some minor changes to your code should resolve the issue. Also added a print to the get_height() call in main since it just returns an integer and you aren't assigning it to anything.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lChild = None
        self.rChild = None

class Tree(object):
    def __init__(self, a_list):
        self.root = self.create_tree(a_list)

    # create a balanced binary search tree from a sorted list
    def create_tree (self, a_list):
       if (len(a_list) <= 0): return None
       mid = (len(a_list))//2 
       root = Node(a_list[mid])
       root.lChild = self.create_tree(a_list[:mid])
       root.rChild = self.create_tree(a_list[mid+1:])
       return root

    def get_height (self, aNode):
       if (aNode == None):
          return -1
       else:
          print(aNode) 
          rHeight = self.get_height(aNode.rChild)
          lHeight = self.get_height(aNode.lChild)
          return (1+rHeight) if rHeight > lHeight else (1+lHeight)

def main():
    new_tree = Tree([1,9,11,17])
    print(new_tree.get_height(new_tree.root))

answered Apr 27, 2019 at 2:43

Andrew L

1,23414 silver badges21 bronze badges

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

1 Comment

curiousP Over a year ago

That's amazing! I got that fixed. Thank you very much sir

Collectives™ on Stack Overflow

Debug Python: Binary Search Tree (Objects bug)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related