Vertical Order Traversal of a Binary Tree using dfs and Map

There is no problem with negative keys, but there are several things missing.

  • A HashMap maintains no order, and even if it did, you are adding elements to the HashMap in depth first order, meaning that the root is added first. So it is quite normal that in your output you don’t get the expected order.

    You should instead iterate the map in order of its key values.

  • When multiple values are added to the same map entry (because the key is the same), you are also adding them in the order that you visit them. But this order is not guaranteed to be the order that is required: a depth first iteration will go up and down through the tree, so there is no guarantee that you will process the upper nodes before the lower nodes. If you wanted that, you would need a breadth-first. Alternatively, you can pass the y-coordinate (the level) as argument.

  • When two nodes have the same x and y coordinate their values should be reported in ascending order. You have no provision for that. If you stick with depth-first, then in a map entry you would need another map keyed by y-coordinate. Then when you find that there is already an entry there for your current y-coordinate, you should make sure you add the current node’s value in the right order. Note that this adds a nesting level to your data structure. It would probably be best to first add the value without sorting, and then have a final phase in your algorithm where you traverse the complete data structure and sort all these little sub arrays.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top