0
\$\begingroup\$

I have used a HashMap of ArrayLists to maintain the nodes at each depth. Also i maintained a depth at each node in the binary tree by using a HashMap that stores . While traversing the tree in a breadth first manner, store the depth of each node(just one more than the depth of its parent) in the hashmap and add the node to the queue. And add each element from the queue to the ArrayList corresponding to its depth in the binary tree.

import java.util.Collection;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class Solution {

    public List<List<Integer>> levelOrder(TreeNode root)
    {
        List<List<Integer>> outputList = new ArrayList<List<Integer>>();
        if(root == null)
        {
            return outputList;
        }
        Queue<TreeNode> queue =  new LinkedList<TreeNode>();
        HashMap<Integer, ArrayList<Integer>> haMap = new HashMap<>();
        HashMap<TreeNode, Integer> nodeDepth = new HashMap<>();
        nodeDepth.put(root,0);
        queue.add(root);
        ArrayList<Integer>  tempList;
        while(!queue.isEmpty())
        {
            root = (TreeNode) queue.poll();
            if(root.left != null)
            {
                nodeDepth.put(root.left, nodeDepth.get(root)+1);
                queue.add(root.left);
            }
            if(root.right != null)
            {
                nodeDepth.put(root.right, nodeDepth.get(root)+1);
                queue.add(root.right);
            }
            if(haMap.containsKey(nodeDepth.get(root)))
            {
                tempList = haMap.get(nodeDepth.get(root));
                tempList.add(root.val);
                haMap.put(nodeDepth.get(root), tempList);
            }
            else
            {
                tempList = new ArrayList<>();
                tempList.add(root.val);
                haMap.put(nodeDepth.get(root), tempList);
            }
        }

        //List<List<Integer>> outputList = new ArrayList<List<Integer>>();

        outputList.addAll(haMap.values());

        return outputList;

    }


}
\$\endgroup\$
1
\$\begingroup\$

Are TreeNode and Solution in separate files? If the shown code is a single file, then it will not compile as you cannot have 2 top-level classes in the same file in Java.

Edit: Turns out it's fine as long as there is only one top-level public class.

Otherwise, just a few minor issues that I can see.

Diamond Operators

You have used the diamond operator <> for haMap and nodeDepth, but you should also use it on outputList and queue.

For example, instead of initializing outputList like:

List<List<Integer>> outputList = new ArrayList<List<Integer>>();

you should initialize it like:

List<List<Integer>> outputList = new ArrayList<>();

and similarly for queue, just like how you did for haMap and nodeDepth.

Favor interfaces over classes

When you define your collections, you should use an interface instead of specifying a specific implementation. That way you can change the implementation easily.

For example, you have done this for outputList and queue, but you should also do it for haMap, nodeDepth, and tempList.

haMap should be defined as:

Map<Integer, List<Integer>> haMap = new HashMap<>();

and similarly for nodeDepth.

Variable Names

Some of your variable names are decent, such as nodeDepth and outputList. They tell me what the object is used for as opposed to what it is. However, queue and haMap could be better. What is queue a queue of? What is being stored in haMap?

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback. Its really helpful. The code worked fine with both the classes in the same file. Since there is only one public class with the file name you don't get a compilation error. Can you please let me know if you got a compilation error. Also I have used <> for outputList and queue as well. Can you please let me know where i missed it . \$\endgroup\$ – saneGuy Apr 9 '16 at 18:50
  • \$\begingroup\$ Well what do you know, I guess it does compile. Thanks for teaching me something! As for the <>, I have added an example to that section in my answer. Let me know if that clarifies it. outputList and nodeDepth seem to be the only places you missed it. \$\endgroup\$ – gla3dr Apr 11 '16 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.