How to find the depth of a binary tree | C Programming and Computer Geeks

Search MY Blog

Monday 21 April 2014

How to find the depth of a binary tree


Depth of a binary tree:
Depth of a binary tree is the maximum length of all paths. Nodes from the root to a leaf form a path.
For example, the depth of the binary tree in the below figure is 4, with the longest path through nodes 1, 2, 5, and 7.
Binary Tree Depth
A binary Tree with depth 4

Solution: Depth of a binary tree is the length of the longest path.
If a binary tree has only one node, its depth is 1. If the root node of a binary tree has only a left sub-tree, its depth is the depth of the left sub-tree plus 1(root node). Similarly, its depth is the depth of the right sub-tree plus 1(root node) if the root node has only a right sub-tree. What if the root node has both left sub-tree and right sub-tree? It is the greater/max value of the depth of the left and right sub-trees plus 1(root node).

 For example, the root node of the binary tree in the above figure has both left and right sub-trees. The depth of the left sub-tree rooted at node 2 is 3, and the depth of the right sub-tree 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(Binarytree Node* pRoot)
{
   int nLeft, nRight;
   if(root == NULL)
        return 0;
    nLeft = TreeDepth(pRoot->pLeft);
    nRight = TreeDepth(pRoot->pRight);
    return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);

}

1 comment:

  1. Hey there! Do you use Twitter? I'd like to follow you if that would be okay.
    I'm absolutely enjoying your blog and look forward to new posts.


    my web site ... how to grow taller

    ReplyDelete

Search This Blog