How is recursion working in the code below?

Question

3.00/5 (1 vote)

See more:

This is the code to calculate height/depth of binary tree.

C++

int maxDepth(struct node * node)
{
    int lheight,rheight;
     if(node==NULL)
     return 0;
     
     lheight=maxDepth(node->left);
     rheight=maxDepth(node->right);
     printf("%d %d\n",lheight,rheight);
     if(lheight>rheight)
     return (lheight+1);
     else
     return (rheight+1);
}

when this code is executed i get a output
0 0
1 0
0 0
0 1
2 2

and final answer is 3
there is no addition in the above code and the value returned is 0 how are we getting 1 or 2 as output , can anybody explain this. Thank You.

Posted 8-Jul-14 8:39am

Member 10933212

Add a Solution

Comments

PIEBALDconsult 8-Jul-14 15:55pm

It works the way it does below.

1 solution

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2014-07-08T08:55:00

It's not easy to explain, particularly when I can't see you eyes, and when they start to glaze over...

So I won't try.
Instead, let's talk about what recursion is.
Recursion is the process of using the same code to work out the various parts of a calculation, and is often demonstrated with factorials:

n! = n * (n - 1)!   where n > 0

Which means that while n is greater than zero (so it has a valid terminator to stop execution) you can calculate a factorial by multiplying the number by the factorial of the number less one:

5! = 5 * (5-1) * (5 - 1 - 1) * (5 - 1 - 1 - 1) * (5 - 1 - 1 - 1 - 1)

Your code works in the same way: it works out the depth of each side by using it's own code on each side, then at each stage it returns the largest (plus one to count that level).
So if a node has no sub-nodes, it will return 1 (because the test at the top of the function returns 0 as the depth of non-existent nodes).

That probably doesn't mean much, so draw on paper a "map" of your node structure like this:

  A
 / \
B  C
  / \
 D   E
  \
   F

And then either "walk it through" manually, or use the debugger to run it step by step, looking at the map at the same time.

At some point the "BING!" moment should happen and it'll make sense!

How is recursion working in the code below?

1 solution

Solution 1

Add your solution here

Preview 0

How is recursion working in the code below?

1 solution

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us