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

1. Very much useful article. Kindly keep blogging

Java Training in Chennai

Java Online Training India

2. 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

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

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

3. 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,

4. 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

5. 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

6. Whoa! I’m enjoying the template/theme of this website. It’s simple, yet effective. A lot of times it’s very hard to get that “perfect balance” between superb usability and visual appeal. I must say you’ve done a very good job with this.
AWS Training in Bangalore |Best AWS Training Institute in Bangalore BTM, Marathahalli
AWS Training in Chennai | AWS Training Institute in Chennai Velachery, Tambaram, OMR

7. I appreciate your efforts because it conveys the message of what you are trying to say. It's a great skill to make even the person who doesn't know about the subject could able to understand the subject . Your blogs are understandable and also elaborately described. I hope to read more and more interesting articles from your blog. All the best.
rpa training in bangalore
rpa training in chennai
rpa training in pune
best rpa training in bangalore

8. Read all the information that i've given in above article. It'll give u the whole idea about it.
Best Devops training in sholinganallur
Devops training in velachery
Devops training in annanagar
Devops training in tambaram

9. This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.I like it and help me to development very well.Thank you for this brief explanation and very nice information.Well, got a good knowledge.
python Course in Pune
python Course institute in Chennai
python Training institute in Bangalore

10. I am looking for and I love to post a comment Python training in punethat "The content of your post is awesome" Great work!

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

12. These provided information was really so nice,thanks for giving that post and the more skills to develop after refer that post.Amazon web services Training in Bangalore

13. this is really nice to read..informative post is very good to read..thanks a lot!
data scientist training and placement in hyderabad

14. Thanks for sharing this information. I really like your blog post very much. You have really shared a informative and interesting blog post .