CODEWITHSUNDEEP
c
user1553924
user1553924

Reputation: 31

how does the following code works? finding the depth of the tree?

please explain the working of following code? i am unable to get the recursion.

int depth(struct tree *q)
{ 
    int h1,h2;
    if(q==NULL)
       return 0;
    else
    {
       h1=depth(q->left);
       h2=depth(q->right);
    }
    return (max(h1,h2) +1 );
}

how does recursion work in the above code? how does h1 and h2 get there value?

Upvotes: 0

Views: 83

Answers (1)

SpacedMonkey
SpacedMonkey

Reputation: 2773

Imagine a simple tree with only 3 nodes, 1 root and 2 children

      Node R
     /      \
    /        \
Node A      Node B

The first call to depth takes Node R as it's argument.

Call 1) q is not NULL so depth() is called for Node R left == Node A

Call 2) q is not NULL so depth() is called for Node A left == NULL

Call 3) q is NULL so return 0;

Call 2) h1 = 0; Now call for Node A right = NULL

Call 4) q is NULL so return 0;

Call 2) h1 = 0; h2 = 0; return max(0, 0) + 1

Call 1) h1 = 1; Now call for Node R right = Node B

Call 5) q is not NULL so depth() is called for Node B left == NULL

Call 6) q is NULL so return 0;

Call 5) h1 = 0; Now call for Node B right = NULL

Call 7) q is NULL so return 0;

Call 5) h1 = 0; h2 = 0; return max(0, 0) + 1;

Call 1) h1 = 1; h2 = 1; return max(1, 1) + 1;

Returns 2.

Upvotes: 4

Related Questions