CODEWITHSUNDEEP
python-2.7binary-tree
Avi
Avi

Reputation: 2283

Adding values to missing nodes in binary tree using Python

I have the following binary tree:

..............1
............/....\
...........2......3
........../..\......\
.........4....5.....6
..........\........./
...........8.......7

I would to complete it to a full binary tree by adding (-1) to the nodes that are missing and to get line by line. It means that the tree will look like this:

..............1
............/.....\
...........2.........3
........../..\....../..\
.........4....5....-1.....6
......../.\.../\..../.\../.\
......-1...8.-1.-1.-1.-1.7.-1

The required result will be as followed:

1
2 3
4 5 -1 6
-1 8 -1 -1 -1 -1 7 -1

The code for creating the binary tree is:

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



root =  Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.left.left = Node(7)
root.left.left.right = Node(8)

Upvotes: 0

Views: 478

Answers (1)

fiveobjects
fiveobjects

Reputation: 4289

Only thing is you have to determine the level first and pass it. However, this also can be handled. Fill missing nodes:

def fillMissingNodes(root, level):
    if (root == None):
        return
    if(root.left == None and level > 0):
        root.left = Node(-1)
    if(root.right == None and level > 0):
        root.right = Node(-1)
    fillMissingNodes(root.left, level - 1)
    fillMissingNodes(root.right, level - 1)

fillMissingNodes(root, 3)

Now, you can traverse in any way you want. Here is level order traversing using Queue:

def traverseLevelOrder(q):
    while(q.qsize() > 1):
        current = q.get()
        if(current == None):
            q.put(None)
            print("\n")
        else:
            if(current.left != None):
                q.put(current.left)
            if(current.right != None):
                q.put(current.right)
            print(current.val),

traverseLevelOrder(q)

In case you want to combine filling missing nodes and traversal line order here you go:

def traverseLevelOrderAndFillMissingNodes(q, level):
    while(q.qsize() > 1):
        current = q.get()
        if(current == None):
            q.put(None)
            print("\n")
            level = level - 1
        else:
            if(current.left == None and level > 0):
                current.left = Node(-1)
            if(current.right == None and level > 0):
                current.right = Node(-1)
            if(current.left != None):
                q.put(current.left)
            if(current.right != None):
                q.put(current.right)
            print(current.val),


traverseLevelOrderAndFillMissingNodes(q, 3)

Here is the output:

1 
2 3 
4 5 -1 6 
-1 8 -1 -1 -1 -1 7 -1

Refer to the full running example from github

By the way, you tree creation code is not exactly like you have shown in the diagram. There is a minor issue with left and right (look for 6 and 7 addition). Here is the correct one:

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
root.right.right.left = Node(7)
root.left.left.right = Node(8)

Upvotes: 2

Related Questions