Recursion - Binary tree

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.

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

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.