Saturday, October 22, 2011

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.

6 comments:

  1. Isn't this just a breadth first traversal of a binary tree?

    ReplyDelete
    Replies
    1. Hi Harry,

      In total awe…. So much respect and gratitude to you folks for pulling off such amazing blogs without missing any points No. 11 - Print Binary Trees from Top to Bottom. Kudos!

      I joined the Amazon affiliate site and received my access key id and my secret key.

      There was a problem downloading and saving the secret key so I created another one.

      I am submitting this information to Amazon to complete my affiliate site but Amazon is accepting the information. Amazon S3 (Simple Storage Service) is an object storage with a simple web service interface to store and retrieve any amount of data AWS Tutorial from anywhere on the web.

      I would appreciate any information as to why this may be occurring.

      I look forward to see your next updates.

      Kind Regards,
      Kevin

      Delete
  2. Hello Harry,


    Thanks for highlighting this and indicating about Print Binary Trees from Top to Bottom where more study and thought is necessary.

    If I buy a Route 53 domain name, can I create an email address and use it with gmail? If so, how?
    I do not want to use Work mail, or SES or an EC2 instance.
    All I want is a username, password, and SMTP and whatever else is needed to link my route 53 email to Gmail.

    Very useful article, if I run into challenges along the way, I will share them here.


    Cheers,
    Abhiram

    ReplyDelete
  3. Hey Brother,


    Seems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on No. 11 - Print Binary Trees from Top to Bottom


    We have a t2.micro instance (built from amzn-ami-hvm-2016.09.1.20170119-x86_64-gp2) on which a customized WordPress is deployed. Following various posts here and elsewhere, various parameters for Apache and MySQL have been set to accommodate the 'size' of the host, including the deployment of a swap partition. The site has been running without issue for weeks. AWS Training




    Please keep providing such valuable information.


    Shukran,
    Ajeeth

    ReplyDelete
  4. Hey Brother,

    Such vivid info on the No. 11 - Print Binary Trees from Top to Bottom ! Flabbergasted! Thank you for making the read a smooth sail! AWS Training


    I have just received an email that says, "We're writing to provide you with an electronic invoice for your use of AWS services for the billing period April 1 - April 30, 2018. Additional information regarding your bill, individual service charge details, and your account history are available on the Billing & Cost Management Page."


    Thanks a lot. This was a perfect step-by-step guide. Don’t think it could have been done better.

    Thank you,
    Radhey

    ReplyDelete
  5. Hi Harry,

    In total awe…. So much respect and gratitude to you folks for pulling off such amazing blogs without missing any points No. 11 - Print Binary Trees from Top to Bottom. Kudos!

    I joined the Amazon affiliate site and received my access key id and my secret key.

    There was a problem downloading and saving the secret key so I created another one.

    I am submitting this information to Amazon to complete my affiliate site but Amazon is accepting the information. Amazon S3 (Simple Storage Service) is an object storage with a simple web service interface to store and retrieve any amount of data AWS Tutorial from anywhere on the web.

    I would appreciate any information as to why this may be occurring.

    I look forward to see your next updates.

    Kind Regards,
    Kevin

    ReplyDelete