Printing out a binary tree level by level

Question

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 <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <type_traits>
template <typename T> 
struct Node
{
 T data;
 Node<T>* left;
 Node<T>* right;
 Node (T d, Node<T>* l = nullptr, Node<T>* r = nullptr) : data(d), left(l), right(r) {}
};
template<typename T>
void deleteTree ( Node<T>* n)
{
 if ( !n )
 return;
 deleteTree(n->left);
 deleteTree(n->right);
 delete n;
}
template <typename T>
void printBinaryTree (Node<T>* n )
{
 std::unordered_map<int, std::vector<Node<T>*> > m;
 printBinaryTree (n, m, 0);
 for ( auto& i : m )
 {
 std::cout << " Level " << i.first << ": ";
 for ( auto& j : i.second )
 std::cout << j->data << " ";
 }
 std::cout << std::endl;
}
// print a binary tree level by level
template <typename T>
void printBinaryTree (Node<T>* n, std::unordered_map<int, std::vector<Node<T>*> >& m, int level )
{
 if (n)
 {
 ++level;
 printBinaryTree ( n->left ,m,level);
 printBinaryTree ( n->right,m,level);
 m[level].push_back(n);
 }
}
template <typename ItType>
auto buildBinaryTree (ItType start, ItType end) -> Node<typename std::iterator_traits<ItType>::value_type>*
{
 using T =typename std::iterator_traits<ItType>::value_type;
 auto first = start;
 auto last = std::prev(end);
 if ( first > last ) // error case
 return nullptr;
 else if ( first < last )
 {
 auto mid = first + ( last - first ) / 2; // avoid overflow
 Node<T>* n = new Node<T>(*mid);
 n->left = buildBinaryTree ( first, mid);
 n->right = buildBinaryTree ( mid+1, end);
 return n;
 }
 // equal
 return new Node<T>(*first);
}
template <typename T> 
Node<T>* buildBinaryTree (std::vector<T>& v)
{
 if ( v.empty() )
 return nullptr; 
 std::sort(v.begin(), v.end());
 return buildBinaryTree (v.begin(), v.end()); 
}
int main()
{
 std::vector<int> v { 1,2,3,4,5,6,7,8,9,10 };
 Node<int>* root = buildBinaryTree ( v );
 printBinaryTree (root);
 deleteTree(root);
}

Answer 1

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 <queue>
#include <utility> // for std::pair
template <typename T>
void printBinaryTree(const Node<T> *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<const Node<T>*,int> node_level;
 std::queue<node_level> 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 << " Level " << nl.second << ": ";
 level = nl.second;
 }
 std::cout << n->data << ' ';
 q.push(node_level(n->left, 1 + level));
 q.push(node_level(n->right, 1 + level));
 }
 }
 std::cout << std::endl;
}

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

• bjackfly: I thought about the map v. unordered_map after posting, good call on that. Also, I like your solution a lot as it simplifies things and uses a standard traversal method. Thanks for sharing this with me. +1 and solution check.

Answer 2

1. You should only use single letter variable names for loop variables. Parameters and other local variables should have more descriptive names. For example when I first quickly glanced over the code I saw this printBinaryTree (n, m, 0); and thought "Strange, why is he passing in two nodes?" associating that m has a similar meaning to n. I had to look again before I realized that m is actually a map. Using names like node or map would result in easier readability.

2. void printBinaryTree (Node<T>* n, std::unordered_map<int, std::vector<Node<T>*> >& m, int level) does not print the tree and should therefor not be named such. It collects all nodes on the same level. Better name might have been buildLevelMap

3. buildBinaryTree apparently expects that the elements to be inserted are in order. You swallow the error case by simply returning a nullptr. You should throw an exception instead to make it clear to the caller that this is invalid input.

4. You represent a binary tree by a reference to a node which happens to be the root. However if the caller accidentally replaces it with a reference to a different node memory leaks because some part of the tree is now lost.

   You should encapsulate the tree in a class like BinaryTree which handles the construction of the tree in the constructor or through a factory method and handles the deletion of the nodes in it's destructor. This way the user can pass around an instance of the tree and not even care about how you store the data internally which facilitates encapsulation (although in a templated class this becomes somewhat a moot point). It would also result in more idiomatic C++ by creating an object through a constructor and destroying an object via a destructor rather than calling a delete function.

• bjackfly: Thanks for the comments, this is helpful. Regarding #3, I call a sort to make sure the items are in order. I could throw an exception or have clients handle the null case. In #4, it is fine if they pass an arbitrary node to represent root, it will be treated as root in that case. Definitely could have encapsulated the binary tree and had the destructor handle clean up and was thinking this when creating the deleteMethod. Agree on the naming an variables, good call. +1 upvote for helpful comments.

Answer 3

i have a easier code.......... consider a tree made of nodes of structure

 struct treeNode{
 treeNode *lc;
 element data;
 short int bf;
 treeNode *rc;
};

Tree's depth can be found out using

int depth(treeNode *p){
 if(p==NULL) return 0;
 int l=depth(p->lc);
 int r=depth(p->rc);
 if(l>=r)
 return l+1;
 else
 return r+1;
}

below gotoxy function moves your cursor to the desired position

void gotoxy(int x,int y)
{
printf("%c[%d;%df",0x1B,y,x);
}

Then Printing a Tree can be done as:

void displayTreeUpDown(treeNode * root,int x,int y,int px=0){
if(root==NULL) return;
gotoxy(x,y);
int a=abs(px-x)/2;
cout<<root->data.key;
displayTreeUpDown(root->lc,x-a,y+1,x);
displayTreeUpDown(root->rc,x+a,y+1,x);
}

which can be called using:

display(t,pow(2,depth(t)),1,1);