Top view binary tree problem

#1

https://ide.codingblocks.com/s/54915
https://hack.codingblocks.com/contests/c/511/953
pls tell me why my code is showing wrong output.My insert() function is absolutely correct as i have used it in many questions so pls check my topView() function .

#2

Hey Raghav, your approach is not correct for topview() you can’t find the top view of a binary tree like this. You can implement the approach using a queue.

  • The idea here is to observe that, if we try to see a tree from its top, then only the nodes which are at top in vertical order will be seen.
  • Start BFS from root. Maintain a queue of pairs comprising of node(Node *) type and vertical distance of node from root. Also, maintain a map which should store the node at a particular horizontal distance.
  • While processing a node, just check if any node is there in the map at that vertical distance.
  • If any node is there, it means the node can’t be seen from top, do not consider it. Else, if there is no node at that vertical distance, store that in map and consider for top view.

You can use another approach also by using the map only :

  • create an empty map where each key represents the relative horizontal distance of the node from the root node and value in the map maintains a pair containing node’s value and its level number. Then we do a pre-order traversal of the tree and if current level of a node is less than maximum level seen so far for the same horizontal distance as current node’s or current horizontal distance is seen for the first time, we update the value and the level for current horizontal distance in the map. For each node, we recurse for its left subtree by decreasing horizontal distance and increasing level by 1 and recurse for right subtree by increasing both level and horizontal distance by 1.
1 Like