Top View Of Binary Tree Depth First Search Using TreeMap

Question

This is my attempt for coding-ninja question top view of binary tree

https://www.naukri.com/code360/problems/top-view-of-binary-tree_799401?leftPanelTabValue=PROBLEM

I wish to do it with TreeMap only. And by using this logic, I think the TreeMap should only pick up key elements as columns and value as the top most node of a column, because of recursion. I tried making a recursion tree and I think it is okay. Yet, I'm getting wrong outputs.

Since TreeMap only stores key in sorted order, it would also be easier to take them out for the top view. I know the row is NOT being used anywhere and yet I have taken it. And shouldn't it work without the row variable? 'Cause recursion should be able to take care of depth first search. And the column variable for insertion in tree map.

It's NOT even passing any test case. But I feel I should be getting the output exactly correct according to recursion tree. OR maybe, I'm making the recursion tree wrong.

For a column, it should only insert the node if it is absent. if it is already there, then that is because it was the highest possible node at that column because of the manner of DFS.

Since, it should be stored int he TreeMap in sorted order, I took them out straight and inserted them in list of integers ans

public static void verticalNodes(TreeNode root, TreeMap<Integer, Integer> solve, int row, int col) {
    if (root == null) {
        return;
    }
    solve.putIfAbsent(col, root.data);
    verticalNodes(root.left, solve, row + 1, col - 1);
    verticalNodes(root.right, solve, row + 1, col + 1);        
}

And for putting nodes in a list of integers of the top View -

public static List<Integer> getTopView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    TreeMap<Integer, Integer> solve = new TreeMap<>();
    verticalNodes(root, solve, 0, 0);
    for (int val : solve.values()) {
        ans.add(val);
    }        
    return ans;
}

Answer 1

Your algorithm is not correct. With a depth first traversal you are not sure you'll visit a column's top node before any other nodes in that same column.

Consider this tree:

   1
  / \
 2   3
  \
   4
    \
     5

The depth first search will first recur into the left branch down to node 5, and register that value for column 1. When later node 3 is visited, that value will not be written to your TreeMap.

You need to rethink this. Hint: use breadth-first.