I have a binary tree generated as follows
class Node:
def __init__(self,data):
# Left Child
self.left = None
# Right Child
self.right = None
# Node Value
self.data = data
def insert(self, data):
# Compare the new value with the parent node
if self.data:
# Less than or equal goes to the Left
if data <= self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
# Greater than goes to the right
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
Now suppose we populate the binary tree with the following
Numbers = [4, 7, 9, 1 , 3]
for index in range(len(Numbers)):
if index == 0:
root = Node(Numbers[index])
else:
root.insert(Numbers[index])
Which generates the following binary tree:
4
/ \
1 7
/ \ / \
. 3 . 9
I have written the following to print the binary tree:
def PrintTree(self, root):
thislevel = [root]
while thislevel:
nextlevel = list()
Curr_Level = ""
for n in thislevel:
Curr_Level += " " + str(n.data)
if n.left:
nextlevel.append(n.left)
if n.right:
nextlevel.append(n.right)
print(Curr_Level)
thislevel = nextlevel
root.PrintTree(root=root)
which generates the following output
4
1 7
3 9
However, I would like the code print the empty entries with an "@", i.e. I want my code to output the following:
4
1 7
@ 3 @ 9
How can I go about adjusting my PrintTree function to achieve this?
Run a modified version of BFS. More specifically, run breadth first search (BFS) starting from the root node. This will assign a level to each node. During BFS, when a current node has a missing child, add an @ node in its place to the FIFO queue. Print a node each time it is removed from the queue. Print in a new line each time a node with a new level is removed from the queue.