Tree : Generate the Top- View of BST

Following the previous post on BF traversal of BSTrees, here is another cool problem often can be easily described using two different data structures. A dictionary and a Tree at play. Please read along ..

Problem

Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order.

A node x is there in output if x is the topmost node at its horizontal distance. Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.

1
    /     \
   2       3
  /  \    / \
 4    5  6   7
Top view of the above binary tree is
4 2 1 3 7
1
      /   \
    2       3
      \   
        4  
          \
           5
            \
              6
Top view of the above binary tree is
2 1 3 6

Approach

We take into account the vertical distance of each node from root, (lets say l for level), and the horizontal distance (d- diameter)of each node from root. We maintain a dictionary to capture the farthest nodes in each side of each level of the tree. Finally we print this dictionary in the order of the distance.

1. We use the two variables, one for vertical distance of current node from the root, and another for the horizontal distance of the current node from the root. Initially root is at (0,0).
2. We use a dictionary with keys representing the horizontal distances from root. If root is at 0, all nodes to the left will be negative distance (e.g. -1, -2,-3...), and all nodes to the right of the root will be at positive values(+1,+2,+3...)
Therefore, we use the horizontal distance for keys in the map.
3. Map values at key d, are the information of a node at distance d (found so far), and the level where that node resides.
4. The trick here is, we keep only data of all lesser levels. For example if m[2] == (node_value, 4)i.e. the value at distance 4 i.e. 4 nodes to right is at level 4. But now we find a node at distance 2 at level 2, then we will replace m[2] with level 2 node.
So, If one node with the same horizontal distance d is encountered while traversing, we check if depth of new node is lower or higher with respect to the value at d (i.e. same horizontal distance) in the map. If depth of new node is lower, then we replace it.
5. Finally we print the nodes in the order of ascending keys.

Code

def fillMap(root, d, l, m): 
    if(root == None): 
        return
if d not in m: 
        m[d] = [root.data,l] 
    elif (m[d][1] > l): 
        m[d] = [root.data,l]
fillMap(root.left, d - 1, l + 1, m) 
    fillMap(root.right, d + 1, l + 1, m)
function should print the topView of 
# the binary tree 
def topView(root):    
    # map to store the pair of node value and its level  
    # with respect to the vertical distance from root.  
    m = {}     
    
    fillMap(root, 0, 0, m) 
    for it in sorted (m.keys()): 
        print(m[it][0], end = " ")

Input

116
37 23 108 59 86 64 94 14 105 17 111 65 55 31 79 97 78 25 50 22 66 46 104 98 81 90 68 40 103 77 74 18 69 82 41 4 48 83 67 6 2 95 54 100 99 84 34 88 27 72 32 62 9 56 109 115 33 15 91 29 85 114 112 20 26 30 93 96 87 42 38 60 7 73 35 12 10 57 80 13 52 44 16 70 8 39 107 106 63 24 92 45 75 116 5 61 49 101 71 11 53 43 102 110 1 58 36 28 76 47 113 21 89 51 19 3

Expected Input:

Here the dictionary is : {0: [37, 0], -1: [23, 1], -2: [14, 2], -3: [4, 3], -4: [2, 4], -5: [1, 5], 1: [108, 1], 2: [111, 2], 3: [115, 3], 4: [116, 4], 5: [83, 9], 6: [84, 10], 7: [85, 11]}

1 2 4 14 23 37 108 111 115 116 83 84 85