No. 35 - Depth of Binary Trees

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.

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.