Tree bottom view

#1

Although I have solved the problem but could u provide a better approach for the same ?

#2

This problem can be easily solved with the help of Hashing. The idea is to 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 more than or equal to 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.

Another approach can be using a queue.

  • The idea here is to observe that, if we try to see a tree from its bottom, then only the nodes which are at bottom 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.
  • As you reach a node , simply update its vertical distance key value in the map with the data of this current node.
  • Only the last nodes of each vertical line will remain in the map while all other previous nodes will get overwritten.
  • Print the values in the map.