Question 1: 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.
Iterative Solution:
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.
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.
Read full article from Coding Interview Questions: No. 35 - Depth of Binary Trees
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);
}
http://massivealgorithms.blogspot.com/2014/07/maximum-height-depth-of-binary-tree.htmlIterative Solution:
We could apply the same in-order traversal of a BST in the binary tree. By saying “in-order” traversal I mean traversing the tree such that it reaches the leaf first (deepest). In other words, we are doing a Depth-first Search (DFS). In fact, all three kinds of tree traversal (pre-order, in-order, and post-order) are doing DFS. Therefore, we could modify any existing iterative solution of tree traversals to solve this problem.
Another solution is to utilize Breadth-first Search (BFS). Unlike DFS, we traverse the tree level by level, thus we are able to obtain the max depth in a direct manner.
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.
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;
}
Solution 1: Visiting Nodes for Multiple Times
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.
Read full article from Coding Interview Questions: No. 35 - Depth of Binary Trees
