Call Trees and the Parts of a Tree

Here is a recursive method:

public static int g(int n) {
  if (n <= 1) {
    return n;
  }
  return g(n / 2) + g(n / 3);
}
Solution
                         g(12)
             ┌─────────────┴─────────────┐
           g(6)                        g(4)
       ┌─────┴───────┐               ┌───┴─────┐
     g(3)          g(2)            g(2)      g(1)
   ┌───┴───┐     ┌───┴───┐       ┌───┴───┐
 g(1)    g(1)  g(1)    g(0)    g(1)    g(0)
Solution
g(12)
  │
g(6)
  │
g(3)
  │
g(1)

It is a chain. Each call makes one recursive call, so each call has one branch below it.

Here is a tree:

                   ╭───╮
                   │ A │
                   ╰─┬─╯
        ┌────────────┼────────────┐
      ╭─┴─╮        ╭─┴─╮        ╭─┴─╮
      │ B │        │ C │        │ D │
      ╰─┬─╯        ╰───╯        ╰─┬─╯
   ┌────┴────┐                    │
 ╭─┴─╮     ╭─┴─╮                ╭─┴─╮
 │ E │     │ F │                │ G │
 ╰─┬─╯     ╰───╯                ╰───╯
   │
 ╭─┴─╮
 │ H │
 ╰───╯
Solution
  • The root is A.
  • The leaves are H, F, C, and G.
  • The internal nodes are A, B, E, and D.
  • The parent of G is D.
  • The children of B are E and F.
  • The siblings of C are B and D.
  • The subtree rooted at B holds B, E, F, and H.
Solution

The height of the tree is 3, from the path A, B, E, H. The depth of G is 2, from the path A, D, G. The height of the subtree rooted at D is 1.

Solution

A binary tree is either the empty tree, or a node holding a value with a left binary tree and a right binary tree. The empty tree plays the role of the base case: it is where the definition stops referring to itself.