No. 11 - Print Binary Trees from Top to Bottom

Problem: Please print a binary tree from its top level to bottom level, and print nodes from left to right if they are in same level. 

For example, it prints the binary tree in Figure 1 in order of 8, 6, 10, 5, 7, 9, 11.

A binary tree node is defined as below:

struct BinaryTreeNode

{

    int                    m_nValue;

    BinaryTreeNode*        m_pLeft; 

    BinaryTreeNode*        m_pRight;

};

Figure 1: A binary tree sample. If it is printed from top to bottom, it prints 8, 6, 10, 5, 7, 9, 11 sequentially.

Analysis: It examines candidates’ understanding of tree traverse algorithms, but the traverse here is not the traditional pre-order, in-order or post-order traverses. If we are not familiar with it, we may analyze the printing process with some examples during interview. Let us take the binary tree in Figure 1 as an example.

Since we begin to print from the top level of the tree in Figure 1, we can start our analysis from its root node. Firstly we print the value in its root node, which is 8. We need to store the children nodes with value 6 and 10 in a data container in order to print them after we print the root. There are two nodes in our container at this time.

Secondly we retrieve the node 6 from the container, since nodes 6 and 10 are in same level and we need to print them from left to right. We also need to store the nodes 5 and 7 after we print the node 6. There are three nodes in the container now, which are node 10, 5 and 7.

Thirdly we retrieve the node 10 from the container. It is noticeable that node 10 is stored into the container before nodes 5 and 7 are stored, and it is also retrieved ahead of nodes 5 and 7. It is typically “First in first out”, so the container is essentially a queue. After print the node 10, we store its two children nodes 9 and 11 into the container too.

Since nodes 5, 7, 9, 11 do not have children, we print them in order.

The printing process can be summarized in the following Table 1:

Step	Operation	Nodes in queue
1	Print Node 8	Node 6, Node 10
2	Print Node 6	Node 10, Node 5, Node 7
3	Print Node 10	Node 5, Node 7, Node 9, Node 11
4	Print Node 5	Node 7, Node 9, Node 11
5	Print Node 7	Node 9, Node 11
6	Print Node 9	Node 11
7	Print Node 11

Table 1: The process to print the binary tree in Figure 1 from top to bottom

We can summarize the rules to print a binary tree from top level to bottom level: Once we print a node, we store its children nodes into a queue if it has. We continue to print the head of the queue, pop it from the queue and store its children until there are no nodes left in the queue.

The following sample code is based on the deque class of STL:

void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot)

{

    if(!pTreeRoot)

        return;

    std::deque<BinaryTreeNode *> dequeTreeNode;

    dequeTreeNode.push_back(pTreeRoot);

    while(dequeTreeNode.size())

    {

        BinaryTreeNode *pNode = dequeTreeNode.front();

        dequeTreeNode.pop_front();

        printf("%d ", pNode->m_nValue);

        if(pNode->m_pLeft)

            dequeTreeNode.push_back(pNode->m_pLeft);

        if(pNode->m_pRight)

            dequeTreeNode.push_back(pNode->m_pRight);

    }

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.