Recursion and Traversal Code

You already used recursion

In the traversals lesson, "traverse the entire left subtree" meant: do the same three tasks again, on a smaller tree. Look again at the three-task rule : the rule uses itself. For example, in pre-order:

The same idea works on the folders in your phone, because a folder system is a tree too: a folder is a node, and the folders inside it are its children. Say you want to list every file in your Documents folder. The rule for any folder: (1) list the files in it; (2) for each folder inside, use this same rule.

It works on bigger folder trees too, like the folder tree from the Trees lesson .

Recursion in Java: a countdown

Before trees, here is a Java method that calls itself and then stops. There are no tree nodes yet, so it is easy to follow. The call countDown(3); prints 3 2 1 Go!, like a New Year countdown.

 1static void countDown(int n) {
 2  if (n == 0) {                  // base case
 3    System.out.println("Go!");
 4    return;
 5  }
 6  System.out.print(n + " ");
 7  countDown(n - 1);              // calls itself
 8}

base caserecursive case

• Base case, lines 2 to 5: when n is 0, print Go! and stop.
• Recursive case, lines 6 and 7: print n, then call itself with a smaller number.

Step through it. The "Call stack" box in the picture lists the calls that have started but not finished. Its colors mean:

runningpaused, waitingending (returning)

 1static void countDown(int n) { 2  if (n == 0) {                  // base case 3    System.out.println("Go!"); 4    return; 5  } 6  System.out.print(n + " "); 7  countDown(n - 1);              // calls itself 8}

We only wrote one call, countDown(3);. Line 7 made the others. This table sums them up:

Why does it stop? Each call uses a smaller number, and at 0 it returns without calling itself again. A recursive method needs both: a base case, and calls that get closer to it each time. (Like the registrar line: each question goes to someone nearer the front.)

How the code does N, L, R

By hand, every node had three tasks. This table matches each task to its line of code:

Some of these lines use Java you may not have read aloud before. This table shows how to read each one:

What is a call stack?

When method A calls method B, Java pauses A and runs B. When B finishes, A continues from where it paused. In recursion, A and B are the same method: the call for 20 pauses while a new call for 10 runs. Java keeps a list of every unfinished call: the call stack.

Java works the same way: a new call goes on top, and only the top call runs. When it finishes, it is removed, and the call below continues where it paused. Remember the Stacks lesson? It listed "method calls" as a stack use. A new call is a push, and a finished call is a pop (last in, first out). Java does them for us.

Trace preOrder, step by step

Many preOrder calls run, one after another. To tell them apart, we give each call a short name, using the node it works on:

We call preOrder(root); on a small tree: 20, with 10 on its left and 30 on its right. In the picture, the tag node shows where the running call's node points. Light teal nodes are already printed.

runningpaused, waitingending (returning)

 1static void preOrder(TreeNode node) { 2  if (node == null) { return; }        // stop 3  System.out.print(node.data + " ");   // N 4  preOrder(node.left);                 // L 5  preOrder(node.right);                // R 6}

What happens at a leaf?

A leaf has no children, but its call still runs every line. It prints, then makes two calls on its empty spots, and each of those stops at line 2.

inOrder: waiting to print

In inOrder, a node waits to print. Here is inOrder(root) on the small tree (20, with 10 on its left and 30 on its right), in four steps:

1. inOrder(20) calls inOrder(10) at line 3, then pauses. It has not printed yet.
2. inOrder(10) calls its empty left side, which returns right away. Then line 4 prints 10. Its empty right side returns too.
3. inOrder(10) is finished. inOrder(20) continues at line 4 and prints 20.
4. Line 5 calls inOrder(30), which prints 30.

Console10 20 30

Step 3 is the key: 20 waits until its whole left side is done, then prints. Switch the order in the call stack lab to watch it wait on the bigger tree.

The key step: at 50

Only one call changes the tree. The call for 50 was paused at line 7, and the call below it just gave back node 45. The picture shows the tree before and after line 7 finishes:

The calls for 60 and 40 do the same two steps (save, then return), but they save the child that was already there, so nothing changes.

Empty tree and duplicates

Empty tree: root = insertRec(null, 7); node is null, so line 4 returns a new node 7, and root = saves it. Now 7 is the root.

Value already there: insertRec(root, 30) goes 40 → 20 → 30. At 30 the value is equal, so neither line 7 nor line 9 runs. Line 11 returns node 30 unchanged. Nothing is added (our BSTs skip duplicates).

Inside a class

Books often put the methods inside a BinarySearchTree class, with the root stored in the class:

class BinarySearchTree {
  Node root;
  void insert(int key) {
    root = insertRec(root, key);
  }
  Node insertRec(Node root, int key) {
    if (root == null) {
      return new Node(key);
    }
    if (key < root.key)
      root.left = insertRec(root.left, key);
    else if (key > root.key)
      root.right = insertRec(root.right, key);
    return root;
  }
}

Use it like this:

BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);

• bst is our variable referring to a BinarySearchTree object.
• insert does root = insertRec(root, key); for you.
• The logic is the same as our insertRec. You will see this class again in "Find the 4 bugs" (Part 6).