**: How 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.**

__Question 1__Figure 1: A binary Tree with depth 4 |

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

__Analysis:__
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:

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);

}

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

__Question 2:__

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

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.

Check this for c# interview questions

ReplyDelete@ http://skillgun.com

Very much useful article. Kindly keep blogging

DeleteJava Training in Chennai

Java Online Training India

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:

ReplyDeleteIsBalanced 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

Hello There,

ReplyDeleteA 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