Inserting a node in to binary tree

Question

I am trying to implement a Binary Tree and the supporting methods for inserting a node in to it, traversing it and so on. I have a peculiar case where my code goes in to a loop or waits too long to return for a certain input. Given the problem I am facing I thought it is unique and hence I am posting it.I am trying to understand what I might have done wrong. Following is my code:

# Create a class for the node data structure


    class Node:
        data = None
        left = None
        right = None
        depth = 0

        # Create a node with some data
        def __init__(self, data):
            self.data = data

        # Set a left node to this node
        def set_left(self, lnode):
            self.left = lnode

        def set_right(self, rnode):
            self.right = rnode

        def get_left(self):
           return self.left.data

        def is_leaf(self):
           if self.left is None and self.right is None:
               return True
           return



       def has_left(self):
           if self.left:
               return True
           return False

       def has_right(self):
           if self.right:
              return True
           return False
# Class for the Btree 
class BTree:
    root = None

    # Create a tree with a base node
    def __init__(self,root):
        self.root = root
        self.count = 0

    # Add node based on the value it's holding

    def insert_node(self,node):
        prev = temp = self.root
        # Traverse until you find the right place to insert the node
        print("Inserting node {}".format(node.data))
        while temp is not None:
            prev = temp
            if node.data < temp.data:
                temp = temp.left
                continue
            if node.data > temp.data:
                temp = temp.right
                continue

        # Go ahead and insert the node here
        if node.data < prev.data:
            prev.set_left(node)
        if node.data > prev.data:
            prev.set_right(node)
    '''
    Pre-order traversal
    Visit the root
    Visit the left subtree
    Visit the right subtree
    '''

    def traverse_pre(self,root):
        # Start with the root
        if root:
            self.count += 1
            print("{}".format(root.data))
            self.traverse_pre(root.left)
            self.traverse_pre(root.right)

    def maxdepth(self, node):
        if node is None:
            return 0
        else:
            # Compute the depth of each subtree
            ldepth = self.maxdepth(node.left)
            rdepth = self.maxdepth(node.right)

            return max(ldepth, rdepth) + 1



if __name__ == '__main__':
    rt = Node(10)
    btree = BTree(rt)
    lst = [14,15,4,9,7,18,5,6,3,54,78,10,100,13,12,11]
    nodes = []
    for i in lst:
        nodes.append(Node(i))
    for node in nodes:
        btree.insert_node(node)
    btree.traverse_pre(rt)
    print("The node count is {}".format(btree.count))
    print(btree.maxdepth(rt))

I have no problems with the input

[14,15,4,9,7,18,5,6,3,54,78,100,13,12,11]

but when I feed an input with a just an extra 10, i.e

[14,15,4,9,7,18,5,6,3,54,78,10,100,13,12,11]

I see that the program never returns and waits/run indefinitely, Can anyone help me understand the problem here ?

You are right, I forgot that i added a root with element 10, how do I handle duplicate entries? — Aparna Chaganti
– Aparna Chaganti, Commented Feb 3, 2018 at 3:21

johnashu · Accepted Answer · 2018-02-03 04:37:21Z

1

You have the starting number 10 in the list..

first make the '10' into a variable, n2

n2 = 10
rt = Node(n2)
...

add some duplicates in and of course the offending number 10

lst = [14,15,4,9,7,18,5,6,3,54,78,100,13,12,11,12,12, 10]

Change the lst into a set, this will not allow duplicates and will remove any.

lst_set = set()

change lst to lst_set. We use add for sets in python, not append

for i in lst:
    lst_set.add(i)

nodes = []
for i in lst_set:

Final check to make sure it is not the original n2 number.

    if i != n2:
        nodes.append(Node(i))

Of course this assumes that your original data is in the form of a list.. If you start with a set you can avoid the conversion from a list.

answered Feb 3, 2018 at 4:37

johnashu

2,2114 gold badges23 silver badges46 bronze badges

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

Collectives™ on Stack Overflow

Inserting a node in to binary tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related