Print top view of binary tree

Example:
# Python3 program to print top
# view of binary tree


# Binary Tree Node
""" utility that allocates a newNode
with the given key """




class newNode:


# Construct to create a newNode
def __init__(self, key):
self.data = key
self.left = None
self.right = None
self.hd = 0


# function should print the top view
# of the binary tree




def topview(root):


if(root == None):
return
q = []
m = dict()
hd = 0
root.hd = hd


# push node and horizontal
# distance to queue
q.append(root)


while(len(q)):
root = q[0]
hd = root.hd


# count function returns 1 if the
# container contains an element
# whose key is equivalent to hd,
# or returns zero otherwise.
if hd not in m:
m[hd] = root.data
if(root.left):
root.left.hd = hd - 1
q.append(root.left)


if(root.right):
root.right.hd = hd + 1
q.append(root.right)


q.pop(0)
for i in sorted(m):
print(m[i], end=" ")




# Driver Code
if __name__ == '__main__':


""" Create the following Binary Tree
1
/ \
2 3
\
  4
    \
       5
         \
           6
"""
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.right = newNode(4)
root.left.right.right = newNode(5)
root.left.right.right.right = newNode(6)
print("The top view of the tree is: ")
topview(root).

Explanation:

Initial Checks and Setup: The function first checks if the root is None. If so, it returns immediately.

Queue Initialization: A queue q is used to perform a level order traversal (BFS). A dictionary m stores the first node at each horizontal distance encountered.

Horizontal Distance (hd): The root node’s horizontal distance is initialized to 0.

Level Order Traversal (BFS):

The root node is added to the queue.

The while loop runs as long as there are nodes in the queue.

For each node:

The node is removed from the front of the queue.

Its horizontal distance (hd) is checked. If this hd is not in the dictionary m, the node’s data is added to the dictionary.

The left child (if it exists) is added to the queue with a horizontal distance of hd – 1.

The right child (if it exists) is added to the queue with a horizontal distance of hd + 1.

The node is then removed from the queue.

Printing the Top View:

After the traversal, the dictionary m contains the top view nodes.

The dictionary is sorted by the horizontal distance, and the node values are printed.