title: HashMap Space Complexity
body: <p>Here's a sample solution for "<a href="https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/#/description" rel="noreferrer">Populating Next Right Pointers in Each Node</a>" puzzle: </p>
  
  <blockquote>
    <p>Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.</p>
  </blockquote>
  
  <pre><code>public void connect(Node root) {
      HashMap&lt;Integer,List&lt;Node&gt;&gt; map = new HashMap&lt;Integer,List&lt;Node&gt;&gt;();
      traverse(root, map , 0);
  }
  
  private void traverse(Node root, HashMap&lt;Integer,List&lt;Node&gt;&gt; map , int level){
  
      if(root != null){
  
          if(map.containsKey(level)){
              List&lt;Node&gt; temp = map.get(level);
              Node set = temp.get(temp.size() -1 );
              set.next = root;
              root.next = null;
              temp.add(root);
              map.put(level,temp);
          }
          else{
              root.next = null;
              List&lt;Node&gt; temp = new ArrayList&lt;Node&gt;();
              temp.add(root);
              map.put(level,temp);
          }
          level++;
          traverse(root.left, map , level);
          traverse(root.right, map,level);
          System.out.println("test");
      }
  }
  </code></pre>
  
  <p>The solution itself doesn't really matter, but what I'm struggling with is determining its Space complexity:</p>
  
  <p>Logically the type of object we are storing in a HashMap should make a difference on its Space complexity, but how we can determine it by having the key and value of the map? </p>
  
  <p>In other words, if we are storing just 5 keys (for 5 nodes) in this map, can we conclude that the space complexity of <code>HashMap&lt;Integer,List&lt;Node&gt;&gt; map = new HashMap&lt;Integer,List&lt;Node&gt;&gt;();</code> is just <code>O(n)</code> or since the value of those keys are a <code>List</code> is should be more than that?</p>