Insertion in Binary Tree (Not BST) Python

Question

I'm trying to insert a node in my binary tree. However, I don't know the proper way to do this. I understand that I should run a bfs and insert in the first null position. How do I translate that into a code?

I was trying with DFS: The tree looks like this:

class Node:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
def insert(node, val):
     if not node:
           return Node(val)
     if not node.left:
           node.left = Node(val)
           return 
     if not node.right:
           node.right = Node(val)
           return 
     return insert(node.left, val)
     return insert(node.right, val)

n1, n2, n3, n4, n5, n6, n7, n8 = Node(1), Node(2), Node(3), Node(4), Node(5), Node(6), Node(7), Node(8)
n1.left, n1.right, n2.left, n2.right, n3.left, n3.right, n4.left = n2, n3, n4, n5, n6, n7, n8

But that gives me an unreachable code. What is the proper way to do this? I'm pretty frustrated by the people calling Binary Tree where they really mean BST.

Can you fix the indentation in your question first? It helps to know what are actual errors and what are artifacts of posting the code on SO. — cosinepenguin
– cosinepenguin, Commented Jul 6, 2017 at 20:45
Actually there are quite a few errors in that code... what are n.left and n.right doing? I don't think you ever declare 'n'. — cosinepenguin
– cosinepenguin, Commented Jul 6, 2017 at 20:51
the indentations are ok I guess. the def is indeed outside of the class — QuestionEverything
– QuestionEverything, Commented Jul 6, 2017 at 20:51
Awesome can we also see how you're implementing the tree itself? — cosinepenguin
– cosinepenguin, Commented Jul 6, 2017 at 20:53

Damel Lambert-Powell · Accepted Answer · 2017-07-09 15:18:50Z

Yeah you're 100% right if you want it to be balanced and don't care about the order of the values inserts should be breadth-first and so I modified the code a little more for you but what I said originally still stands:

To do a bfs traversal you have to use another data structure, a queue. Queues are FIFO this means you end up visiting each node at each level before going to the next. Interestingly to make this depth first pop from the end instead of the beginning to simulate a stack.

def insert(node, val):
    """
    Always returns the root of the tree
    """
    if not node:
        return Node(val)
    queue = [node]
    while len(queue) > 0:
        # n is the current node in the tree
        n = queue.pop(0)

        # if it has no children insert node
        # start from the left
        if not n.left:
            n.left = Node(val)
            return node
        if not n.right:
            n.right = Node(val)
            return node

        queue.append(n.left)
        queue.append(n.right)

cosinepenguin · Accepted Answer · 2017-07-06 21:27:06Z

1

Alright! So I hope this is what you are looking for, but your code is very good, it just needs a few changes:

class Node:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

    def __str__(self): #This allows you to print out the nodes for testing, other "magic" methods can be created here too!
        return str(self.val)

def insert(node, val=None):
     if not val:
        return Node(node) #This will create a new node if val is None
     if not node.left:
           node.left = val
           return 
     if not node.right:
           node.right = val
           return 
     return insert(node.left, val)
     return insert(node.right, val)


def main():
     n1 = insert(1)
     n2 = insert(2)
     n3 = insert(3)
     n4 = insert(4)
     n5 = insert(5)
     n6 = insert(6)
     n7 = insert(7)
     n8 = insert(8)

     insert(n1, n2)
     insert(n1, n3)
     insert(n2, n4)
     insert(n2, n5)
     insert(n3, n6)
     insert(n3, n7)
     insert(n4, n8)

     print(n1.left)
     print(n3.left)

main()

This worked for my tests! I changed the logic behind insert() in order to allow the function to create new Nodes (though I know that is not necessarily how you want it done, you can change that back!). There are a plethora of other ways to implement this, though, but this is the closest I could think of that stayed true to your original code.

Hope it helps!

PS Another great resource is Interactive Python (granted the chapter is about BSTs). It can still be useful going forward!

answered Jul 6, 2017 at 21:27

cosinepenguin

1,5751 gold badge13 silver badges22 bronze badges

1 Comment

QuestionEverything Over a year ago

thanks @cosinepenguin . but let's say i already have binary tree. now i want to insert a node here in the first null place availabe. so i would run a bfs and if i find any left or right child as empty, i would insert it there. that was my problem.

Collectives™ on Stack Overflow

Insertion in Binary Tree (Not BST) Python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related