CODEWITHSUNDEEP
javatreebinary-treetree-traversal
DisplayName
DisplayName

Reputation: 67

Vertical Order Traversal of a Binary Tree using dfs and Map

I'm trying to do a Vertical Order Traversal of a Binary Tree, this problem: https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

My Approach: I do a depth first search on each node in the tree, where the root is 0. Anything to the left is the current root - 1 and anything to the right is the current root + 1. I also have a HashMap where the keys are the value of the node (the ones with the same position match) and the values are a linked list of all the TreeNodes who have the same location (the key value).

When I print out the values of my HashMap, I see that it has the right elements grouped together.

The problem is that when I return the final List, the lists of integers are not in the right order which should be from the biggest negative to the biggest positive - instead, the elements in the same position as the root are printed out first. I think this is because I can't use negative numbers as keys for my HashMap -- but I can't figure out a way around this.

For example:

If the input tree is:

enter image description here

The program should return: [[9], [3,15], [20], [7]]

However, mine returns: [[3,15], [9], [20], [7]]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        /*dfs getting value of node & adding it to list*/
        List<List<Integer>> list = new ArrayList<>();
        
        Map<Integer, List<Integer>> map = new HashMap<>();
        
        if(root == null) {
            return list;
        }
        
        dfs(root, map, 0);
        
        for(Map.Entry<Integer, List<Integer>> m : map.entrySet()) {
            List<Integer> temp = new ArrayList<>();
            for(int i : m.getValue()) {
                temp.add(i);
            }
            list.add(temp);
        }
        
        return list;
    }
    
    public static void dfs(TreeNode root,  Map<Integer, List<Integer>> map, int curVal) {
        if(root == null) {
            return;
        }
        
        // System.out.println("root val = " + root.val);
        // System.out.println("curVal = " + curVal);
        
        if(map.containsKey(curVal)) {
            List temp = map.get(curVal);
            temp.add(root.val);
            map.put(curVal, temp);
        }
        else {
            List<Integer> tempList = new ArrayList<>();
            tempList.add(root.val);
            map.put(curVal, tempList);
        }
        
        dfs(root.left, map, curVal - 1);
        dfs(root.right, map, curVal + 1);
    }
}

Upvotes: 0

Views: 605

Answers (1)

trincot
trincot

Reputation: 350760

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.

Upvotes: 0

Related Questions