Recursion - Binary tree

Question

I have this code to find the diameter of the binary tree. Diameter of a binary tree: The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

I am trying to understand the below code and recursion in general. I am trying to dry run with this simple tree. I understand when root is 20 height will become 1 (Max(0,0)+1) and then returning the Math.Max(0+0+1, Max(0,0)). My understanding here is it will set ldiameter to 1 with this return value while root = 10. Is this correct? and at this point lh gets changed to 1. How does it change to 1? Also, if you can help me dry run this simple tree step by step that will be really helpful.

    10
  /    \
 20    30


public int FindDiameter_util(Node root, ref int height)
        {
            /* lh --> Height of left subtree
            rh --> Height of right subtree */
            int lh = 0, rh = 0;

            /* ldiameter  --> diameter of left subtree
               rdiameter  --> Diameter of right subtree */
            int ldiameter = 0, rdiameter = 0;
            if (root == null)
            {
                height = 0;
                return 0; /* diameter is also 0 */
            }
            /* Get the heights of left and right subtrees in lh and rh
              And store the returned values in ldiameter and ldiameter */
            ldiameter = FindDiameter_util(root.left, ref lh);
            rdiameter = FindDiameter_util(root.right, ref rh);

            /* Height of current node is max of heights of left and
               right subtrees plus 1*/
            height = Math.Max(lh, rh) + 1;

            return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter));
        }

Answer 1

Recursivity is a stack-based approach. The recursive calls of a function will be executed earlier than the issuer. You can understand recursion easier if you think about the concept of function composition. Let's look at this example function call:

f(g(x))

As you can see, the parameter of f is g(x), which means that g(x) needs to be calculated first before one executes f(g(x)), therefore g(x) is a dependency of f(g(x)). Now, imagine that g is f as well, so you call

f(f(x))

In a similar way, f(x) is a dependency of f(f(x)), since you cannot calculate f(f(x)) without having the result of f(x).

If you understand this purely mathematical concept, then, the next step is to add the algorithm to f as a context. In programming, f(f(x)) is not necessarily a calculation only, but some state changes might occur in the process.

The next step is to understand the concept of repeated recursion. In our case, we do not know in advance how many times should we call FindDiameter_util from within FindDiameter_util, since it should work for any tree. So, let us analyze this function a little.

Facts:

• leaf nodes are recognized from the fact that root == null, this is the end sign as well (see the return)
• height of leaf nodes is 0
• in a non-trivial case, when the node is not a leaf node, the task is divided into two sub-tasks (left sub-tree and right sub-tree)
• when the result of the sub-tasks is calculated, then the sub-tree of the bigger tree + 1 (we add the current node) is the maximum height

The strategy used here is called Divide et Impera. This is composed of several phases: - divide the task into similar, but smaller sub-task until you reach triviality - conquer the results, getting the response to gradually more complex sub-tasks until you get the answer to the initial question

In our case, the algorithm, in short is going from the root to the leafs until it reaches triviality in all sub-trees, that is determined by the end-sign of root == null and then use the trivial answer to get the answer to the next-to-trivial questions. So, you are going from root to leaf to divide and then back from leaf to root to conquer.

Answer 2

Let's recurse through your simple tree:

   []     <---- root
 /   \
[]    []   <---- children

When the function is initially called, root == 0 will be true, so the input height is initialized to 0:

   [h=0]     <---- root
   /   \
  []    []   <---- children

Then you will set the height at the root for left and right subtrees to 0:

   [h = 0, lh = 0, rh = 0]     <---- root
         /    \
       []      []          <---- children

Then you recurse on the left child, passing in lh as its height parameter:

   [h = 0, lh = 0, rh = 0]     <---- root
         /    \
      [h=0]    []          <---- children

The left child will initialize its height variables for its own left and right subtrees:

        [h = 0, lh = 0, rh = 0]     <---- root
            /          \
   [h=0, lh=0, rh=0]    []          <---- children

Then the left child will attempt to recurse on its own left subtree (even though there isn't one; it's null):

       [h = 0, lh = 0, rh = 0]      <---- root
            /          \
   [h=0, lh=0, rh=0]    []          <---- children
          /
        null

At this null node, we recognize it as such, and return 0, walking back up to the parent, lh gets set to 0 (again, so no change):

       [h = 0, lh = 0, rh = 0]      <---- root
            /          \
   [h=0, lh=0, rh=0]    []          <---- children

Then we recurse on the right subtree, but it too is null:

       [h = 0, lh = 0, rh = 0]      <---- root
            /          \
   [h=0, lh=0, rh=0]    []          <---- children
              \
             null

So we return 0 for its height to the parent, which sets rh to 0 (again):

       [h = 0, lh = 0, rh = 0]      <---- root
            /          \
   [h=0, lh=0, rh=0]    []          <---- children

So far, pretty uninteresting. But now that we know the height of the children's subtrees, we can compute the height at the current tree as max(lh, rh) + 1, which gives us a height of 1 for this leaf (a tree with only a root has height 1, so it makes sense that a subtree with only a root has height 1).

       [h = 0, lh = 0, rh = 0]      <---- root
            /          \
   [h=1, lh=0, rh=0]    []          <---- children

However, the h at this level is actually a reference to lh at the root, so it too becomes 1:

       [h = 0, lh = 1, rh = 0]      <---- root
            /          \
   [h=1, lh=0, rh=0]    []          <---- children

Now the left subtree is done, so we recurse on the right subtree in the same way (details omitted):

         [h = 0, lh = 1, rh = 1]           <---- root
            /               \
   [h=1, lh=0, rh=0]  [h=1, lh=0, rh=0]    <---- children

Now that we've recursed on both subtrees, we return to the root, who now knows the height of its left and right subtrees (both are 1), so it can compute:

height = Math.Max(lh, rh) + 1;

which is

height = Math.Max(1, 1) + 1 = 2

So the root gets its height set to 2:

         [h = 2, lh = 1, rh = 1]           <---- root
            /               \
   [h=1, lh=0, rh=0]  [h=1, lh=0, rh=0]    <---- children

Answer 3

Last line most important here:

return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter));

There are 3 cases for the current tree:

1) longest simple path (for the currenet tree) in the left subtree

2) longest simple path (for the currenet tree) in the right subtree

3) longest simple path consists of 3 pieces: path from the deepest node to the root in the left subtree, current node, path from the root to the deepest node in the right subtree.

We can calculate theese 3 possible diameters recursively and after that choose the maximum of them.