Monday, January 28, 2013

No. 35 - Depth of Binary Trees

Question 1How do you get the depth of a binary tree? Nodes from the root to a leaf form a path. Depth of a binary tree is the maximum length of all paths. For example, the depth of the binary tree in Figure 1 is 4, with the longest path through nodes 1, 2, 5, and 7.
Figure 1: A binary Tree with depth 4
Analysis: We have discussed how to store nodes of a path in a stack while traversing a binary tree in the blog "Paths with Specified Sum in Binary Tree ". The depth of a binary tree is the length of the longest path. This solution works, but it is not the most concise one.
The depth of a binary tree can be gotten in another way. If a binary tree has only one node, its depth is 1. If the root node of a binary tree has only a left subtree, its depth is the depth of the left subtree plus 1. Similarly, its depth is the depth of the right subtree plus 1 if the root node has only a right subtree. What is the depth if the root node has both left subtree and right subtree? It is the greater value of the depth of the left and right subtrees plus 1.
 
For example, the root node of the binary tree in Figure 1 has both left and right subtrees. The depth of the left subtree rooted at node 2 is 3, and the depth of the right subtree rooted at node 3 is 2, so the depth of the whole binary tree is 4; 1 plus the greater value of 3 and 2.
 
It is easy to implement this solution recursively, with little modification on the post-order traversal
algorithm, as shown below:
 
int TreeDepth(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return 0;
    int nLeft = TreeDepth(pRoot->m_pLeft);
    int nRight = TreeDepth(pRoot->m_pRight);
    return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
 
Question 2: How do you verify whether a binary tree is balanced? If the depth difference between a left subtree and right subtree of any node in a binary tree is not greater than 1, it is balanced. For instance, the binary tree in Figure 1 is balanced.
 
Analysis:
 
Solution 1: Visiting Nodes for Multiple Times

According to the definition of balanced binary trees, this problem can be solved by getting the depth difference between the left and right subtrees of every node. When a node is visited, the function depth is invoked to get the depth of its left and right subtrees. If the depth different is 1 at most for all nodes in a binary tree, it is balanced. This solution can be implemented based on the TreeDepth discussed in the preceding problem, as shown below:
 
bool IsBalanced_Solution1(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return true;
    int left = TreeDepth(pRoot->m_pLeft);
    int right = TreeDepth(pRoot->m_pRight);
    int diff = left - right;
    if(diff > 1 || diff < -1)
        return false;
    return IsBalanced_Solution1(pRoot->m_pLeft)
        && IsBalanced_Solution1(pRoot->m_pRight);
} 


This solution looks concise, but it is inefficient because it visits some nodes for multiple times. Take the binary tree in Figure 1 as an example. When the function TreeDepth takes the node 2 as a parameter, it visits nodes 4, 5, and 7. When it verifies whether the binary tree rooted at node 2 is balanced, it visits nodes 4, 5, and 7 again. Obviously, we could improve performance if nodes are visited only once.
 
Solution 2: Visiting Every Node Only Once
 
If a binary tree is scanned with the post-order algorithm, its left and right subtrees are traversed before the root node. If we record the depth of the currently visited node (the depth of a node is the maximum length of paths from the node to its leaf nodes), we can verify whether the subtree rooted at the currently visited node is balanced. If any subtree is unbalanced, the whole tree is unbalanced.
This new solution can be implemented as shown in below:
 
bool IsBalanced_Solution2(BinaryTreeNode* pRoot)
{
    int depth = 0;
    return IsBalanced(pRoot, &depth);
}
bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
{
    if(pRoot == NULL)
    {
        *pDepth = 0;
        return true;
    }
    int left, right;
    if(IsBalanced(pRoot->m_pLeft, &left) && IsBalanced(pRoot->m_pRight, &right))
    {
        int diff = left - right;
        if(diff <= 1 && diff >= -1)
        {
            *pDepth = 1 + (left > right ? left : right);
            return true;
        }
    }
    return false;
}
 
 
After verifying left and right subtrees of a node, the solution verifies the subtree rooted at the current visited node and passes the depth to verify its parent node. When the recursive process returns to the root node finally, the whole binary tree is verified. 
 
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 him via zhedahht@gmail.com . Thanks. 

 

10 comments:

  1. Thanks Harry for this post. I see that the second solution as you mention with passing the depth, is effective, but a question here for clarification:

    IsBalanced function return true and false at every node, so the decision is upto the calling function to break out when he receives a false, correct, so this way, there is no need to go through all the nodes?

    thanks

    ReplyDelete
  2. Hello There,


    A really interesting, clear and easily readable CoderCareer: Discussing Coding Interview Questions article of interesting and different perspectives' will clap. So much is so well covered here.


    FFMPEG is an open source software for video and audio processing and is designed in c and compiled by MinGW32 on Linux machines.
    I want to use this software on windows platform when I open the folder of the software, I will encounter many headers and .c files in different folders. They are not in form of a project and I don't know how can I combine them together and recompile them in windows. Have you encountered in such problem and do you have any idea?


    I read multiple articles and watched many videos about how to use this tool - and was still confused! Your instructions were easy to understand and made the process simple.


    Thanks and Regards,
    Leena

    ReplyDelete
  3. Hi Harry,

    Fully agree on No. 35 - Depth of Binary Trees. We’re seeing a lot of projects tackle big complex problems but few seem to have taken into consideration and in particular reasons to adopt.

    I was trying to create my first ec2 instance but I found that my limit to create gpu instances was 0. I submitted a request to Amazon assuming I would have some response in 24 hours, does anyone know how long it takes to hear back from them regarding limit increases?

    An Amazon Machine Image (AMI) is a template that contains a software configuration (for example, an operating system, an application server, and applications). From an AMI, we launch an instance, which is a copy of the AMI running as a virtual server in the cloud AWS Tutorial . We can even launch multiple instances of an AMI.

    But nice Article Mate! Great Information! Keep up the good work!

    Regards,
    Kevin

    ReplyDelete
  4. Hello Mate,

    I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key No. 35 - Depth of Binary Trees in the entire space.


    Pretty new to all this, just switched to AWS from 1and1. AWS Tutorial They used to track the number of visitors and page views and other stats. How can I do this with AWS, just to see if I'm getting 5 vs 500 visitors per day? Any help/advice is appreciated,

    Appreciate your effort for making such useful blogs and helping the community.

    Thank you,
    Radhey

    ReplyDelete
  5. Hello Mate,


    Grazie! Grazie! Grazie! Your blog is indeed quite interesting around No. 35 - Depth of Binary Trees I agree with you on lot of points!


    There wouldn't be any static charges such as monthly fee for setting up a static website beyond the resources that you are expecting to use. AWS Tutorial The Simple Monthly Calculator in this case would be dependent on the expected Data Transfer, S3 usage and Route 53 config usage.




    Follow my new blog if you interested in just tag along me in any social media platforms!


    Thank you,
    Irene Hynes

    ReplyDelete
  6. Recently, I have commenced a blog the info you give on this site has encouraged and benefited me hugely. Thanks for all of your time & work. BinaryToday.com

    ReplyDelete
  7. Really it was an awesome article,very interesting to read.You have provided an nice article,Thanks for sharing.devops Training in Bangalore

    ReplyDelete
  8. 360DigiTMG, the top-rated organisation among the most prestigious industries around the world, is an educational destination for those looking to pursue their dreams around the globe. The company is changing careers of many people through constant improvement, 360DigiTMG provides an outstanding learning experience and distinguishes itself from the pack. 360DigiTMG is a prominent global presence by offering world-class training. Its main office is in India and subsidiaries across Malaysia, USA, East Asia, Australia, Uk, Netherlands, and the Middle East.

    ReplyDelete