Printing out a binary tree level by level Below is my implementation for an interview question of printing a binary tree level by level. I've also included some methods for creating a binary tree from a vector in my solution.  Please review my solution.

#include &lt;iostream&gt;
#include &lt;unordered_map&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;type_traits&gt;

template &lt;typename T&gt; 
struct Node
{
  T data;
  Node&lt;T&gt;* left;
  Node&lt;T&gt;* right;

  Node (T d, Node&lt;T&gt;* l = nullptr, Node&lt;T&gt;* r = nullptr) : data(d), left(l), right(r) {}
};

template&lt;typename T&gt;
void deleteTree ( Node&lt;T&gt;* n)
{
  if ( !n )
    return;
  deleteTree(n-&gt;left);
  deleteTree(n-&gt;right);
  delete n;
}

template &lt;typename T&gt;
void printBinaryTree (Node&lt;T&gt;* n )
{
  std::unordered_map&lt;int, std::vector&lt;Node&lt;T&gt;*&gt; &gt; m;
  printBinaryTree (n, m, 0);
  for ( auto&amp; i : m )
  {
    std::cout &lt;&lt; " Level " &lt;&lt; i.first &lt;&lt; ": ";
    for ( auto&amp; j : i.second )
      std::cout &lt;&lt; j-&gt;data &lt;&lt; "  ";
  }
  std::cout &lt;&lt; std::endl;
}

// print a binary tree level by level
template &lt;typename T&gt;
void printBinaryTree (Node&lt;T&gt;* n, std::unordered_map&lt;int, std::vector&lt;Node&lt;T&gt;*&gt; &gt;&amp; m, int level )
{
  if (n)
  {
    ++level;
    printBinaryTree ( n-&gt;left ,m,level);
    printBinaryTree ( n-&gt;right,m,level);

    m[level].push_back(n);
  }
}

template &lt;typename ItType&gt;
auto buildBinaryTree (ItType start, ItType end) -&gt; Node&lt;typename std::iterator_traits&lt;ItType&gt;::value_type&gt;*
{
  using T =typename std::iterator_traits&lt;ItType&gt;::value_type;
  auto first = start;
  auto last = std::prev(end);

  if ( first &gt; last ) // error case
    return nullptr;
  else if ( first &lt; last )
  {
    auto mid = first +  ( last - first ) / 2; // avoid overflow
    Node&lt;T&gt;* n = new Node&lt;T&gt;(*mid);
    n-&gt;left = buildBinaryTree ( first, mid);
    n-&gt;right = buildBinaryTree ( mid+1, end);
    return n;
  }

  // equal
  return new Node&lt;T&gt;(*first);
}

template &lt;typename T&gt; 
Node&lt;T&gt;* buildBinaryTree (std::vector&lt;T&gt;&amp; v)
{
  if  ( v.empty() )
   return nullptr; 

  std::sort(v.begin(), v.end());
  return buildBinaryTree (v.begin(), v.end()); 
}

int main()
{
  std::vector&lt;int&gt; v { 1,2,3,4,5,6,7,8,9,10 };
  Node&lt;int&gt;* root = buildBinaryTree ( v );
  printBinaryTree (root);
  deleteTree(root);
}
I got the following output:


Level 1: 5   Level 2: 2  8   Level 4: 4  7  10   Level 3: 1  3  6  9



Printing the layers in a non-deterministic order is probably undesirable behaviour.  You used an unordered_map, which guarantees the order of neither its keys nor its values.  To impose order on the values (the nodes of each level), you store a vector in the map, which complicates the data structure.

The traditional way to do a breadth-first traversal of a tree is to use a queue, and to work iteratively on elements of the queue rather than recursively on elements of the tree.  Not only is this a less complex data structure than an unordered map of ints to vectors of nodes, it also stores nodes from no more than two levels of the tree at a time, rather than all nodes of the tree at once.

#include &lt;queue&gt;
#include &lt;utility&gt;   // for std::pair

template &lt;typename T&gt;
void printBinaryTree(const Node&lt;T&gt; *n) {
    if (nullptr == n) {
        return;
    }
    int level = 0;

    // Use a queue for breadth-first traversal of the tree.  The pair is
    // to keep track of the depth of each node.  (Depth of root node is 1.)
    typedef std::pair&lt;const Node&lt;T&gt;*,int&gt; node_level;
    std::queue&lt;node_level&gt; q;
    q.push(node_level(n, 1));

    while (!q.empty()) {
        node_level nl = q.front();
        q.pop();
        if (nullptr != (n = nl.first)) {
            if (level != nl.second) {
                std::cout &lt;&lt; " Level " &lt;&lt; nl.second &lt;&lt; ": ";
                level = nl.second;
            }
            std::cout &lt;&lt; n-&gt;data &lt;&lt; ' ';
            q.push(node_level(n-&gt;left,  1 + level));
            q.push(node_level(n-&gt;right, 1 + level));
        }
    }
    std::cout &lt;&lt; std::endl;
}


As a final touch, pay attention to the const-correctness of the function's parameter.