Trees and Recursion

Trees are important in Computer Science. They are best defined recursively and therefore are an excellent match for recursive algorithms. It's essential that you are comfortable with such algorithms and data structures.

Recursive Definition:

A binary tree is either:

• a leaf (a node with no children), OR
• a node with two children, each of which is a binary tree

Tree in JSON¶

The JSON structure that we learned earlier in the course is easily able to represent a binary tree:

• a leaf can be just a string or a number or some other atomic value
• a node can be a JS object with two properties, lchild and rchild,
• each of which is a tree (there's the recursion)

Here are some examples. I suggest you draw them out so that you are better able to understand this definition:

tree1 = 1;
tree2 = {lchild: 2, rchild: 3};
tree3 = {lchild: {lchild: 4, rchild: 5}, rchild: {lchild: 6, rchild: 7}};
tree4 = {lchild: 8, rchild: {lchild: 9, rchild: {lchild: 10, rchild: 11}}};

Look at those variables in this browser window and see what they look like. Toggle the triangles to go deeper.

Tree Diagrams¶

Here are the trees I drew for the examples above. Do they match your (mental) pictures?

Pretty-Printing a tree¶

Trying to read a tree like the ones above can be a bit difficult at first. Pretty-printing the tree, nicely indented, can help. One way is to use the JSON.stringify() function with the third argument being a tab character (written as \t). Then the JSON string is nicely indented. Here's how:

JSON.stringify(tree3, null, '\t');

Let's write a simple function called pp that does this:

function pp(json) {
    return JSON.stringify(json, null, '\t');
}

Open the JS console and try that function on the example trees above.

Random Numbers¶

In a moment, we'll build some random trees with random numbers as the leaves, but we'll take a brief aside to talk about random numbers. Most languages have a built-in random number generator that returns decimal values between 0 and 1. That's because such a value is often easy to work with and to transform into other kinds of random numbers. For example, the following function returns true with the given probability:

function chance(prob) {
    if( Math.random() < prob ) {
        return true;
    } else {
        return false;
    }
}

That function is written the way most novices write code, but it's needlessly verbose. Most experienced programmers would realize that the value of the conditional is exactly the value that they want to return, so they would instead write the following, which is much more concise and means exactly the same thing:

function chance(prob) {
    return( Math.random() < prob );
}

I've already defined that function in this page, so you can try it in the JS console. Do that a few times, so that you feel confident using it.

Next, suppose we want to generate equally likely integer numbers from 1 to 6, say for a die roll. The idea is to take the fractional number, multiply it by the number of values we want (6 values, which is just the max minus the min plus 1), and then round it down to an integer (using floor). That yields an integer in the range from [0-5]. Then, add the bottom of the range (in this case, 1), and you get the numbers you want.

function rand_in_range(min,max) {
    range = max - min + 1;
    return( min + Math.floor(range*Math.random()));
}

Again, I've already defined that function in this page, so you can try it in the JS console. Do that a few times, so that you feel confident using it.

Random Tree¶

Let's write a JS function that can create a random tree like the ones above. You can use the pp function to print the results. This function uses random numbers for two purposes. One is random values for the leaves. For that, we'll use random integers from 1-100. The other is the probability of a leaf. For that, we'll use chance.

function randTree(probLeaf) {
    if( chance(probLeaf) ) {
        return rand_in_range(1,100);
    } else {
        return {lchild: randTree(probLeaf),
                rchild: randTree(probLeaf) };
    }
}

Note the two recursive calls to randTree.

As before, try randTree in the JavaScript console and play around with it a bit so that you feel confident using it. I suggest using a probability of a leaf between 0.5 and 0.6. Too low and you'll exhaust the stack size too often. Too high and almost all the trees are tiny and uninteresting. Try a few values. Try it multiple times until you get a non-trivial tree or two. I used the uparrow key to try the following options a few dozen times:

pp(rt=randTree(0.55));
pp(rt=randTree(0.53));

If this were a course in probability, I might ask you to compute the expected size of the tree as a function of the probability of a leaf.

Functions on a Tree¶

How do we write functions that work on recursive data structures? We write recursive functions! Let's work through a specific example. Imagine we want to find the largest value in a random tree of random numbers. What does that mean? Look at the example trees in the earlier section.

• tree1: the largest number is, trivially, 1
• tree2: the largest number is 3
• tree3: the largest number is 7
• tree4: the largest number is 11

Let's look deeper, though. For tree3, which consists of two subtrees, the largest number in the left subtree is 5 and the largest in the right subtree is 7, and the larger of those two is, of course, 7. What that means is that if we have the largest value in each subtree, we can compare them to find the largest value in subtree starting at the current node.

That suggests the following recursive algorithm:

function largestInTree(tree) {
    if( typeof tree === "number" ) {
        // a leaf, so trivially the leaf is the largest value
        return tree;
    } else {
        // recursively compute largest in each subtree
        let largestLeft  = largestInTree(tree.lchild);
        let largestRight = largestInTree(tree.rchild);
        return Math.max(largestLeft, largestRight);
    }
}

I've defined that function in this file. Open a JS console and try it on our example trees, as follows. You can even try it on subtrees and sub-subtrees of our example trees, as shown:

largestInTree(tree1); // 1
largestInTree(tree2); // 3
largestInTree(tree3); // 7
largestInTree(tree4); // 11
largestInTree(tree3.lchild); // 5
largestInTree(tree3.rchild); // 7
largestInTree(tree4.lchild); // 8
largestInTree(tree4.rchild); // 11
largestInTree(tree3.lchild.lchild); // 4
largestInTree(tree3.lchild.rchild); // 5

Code Analysis¶

Let's look back at the recursive function we just wrote.

First, you'll notice it has no loops. It's always tempting to think that you have to use a loop when you have to process multiple things, like all the numbers in a tree, but recursion doesn't rely on loops. A recursive solution needs:

• one or more base cases (non-recursive cases), and
• one or more recursive cases.

In terms of programming constructs, instead of loops we need

• conditionals, and
• recursive function calls

The conditionals (if statements) allow us to determine whether the current node is a base case or not. In recursions over trees, the base cases are almost always the leaf nodes: nodes that have no child nodes. The recursive cases are almost always the nodes that do have children (also called internal nodes), and the recursion works by solving the child nodes by recursively calling the function on each child. The base cases are solved non-recursively.

With that in mind, let's look at our code and imagine invoking it on tree3.

function largestInTree(tree) {  // tree3
    if( typeof tree === "number" ) {
        // a leaf, so trivially the leaf is the largest value
        return tree;
    } else {
        // recursively compute largest in each subtree
        let largestLeft  = largestInTree(tree.lchild); // f(tree3.lchild) returns 5
        let largestRight = largestInTree(tree.rchild); // f(tree3.rchild) returns 7
        return Math.max(largestLeft, largestRight); // returns 7
    }
}

Understanding recursive code is always difficult. In understanding ordinary code, we're used to imagining each step in our minds and walking through the code, but that's very hard with recursive code.

Instead, I suggest you use a leap of faith and just trust that the recursive case will work. As long as the function works for each individual case (each branch of the if statements) and we trust that the recursive calls work and return the correct value, the whole function will work.

Let's see what that means for our largestInTree function. There are two cases we have to think about:

1. the base case, which is just a single number. In that case, the function returns the number which is clearly the largest value in the one-node "tree" that is a single number. (Remember that our recursive definition of a tree includes a base case that is a single value.) SOLVED.
2. the other case, where the node in the tree has two child nodes (subtrees). If we trust that the two recursive calls work and return the largest value in that subtree, then all we have to do is return whichever one is bigger, which is the biggest one in the tree starting from us. SOLVED

In our leap of faith above, we assumed that the recursive call on the left child and right child worked. We can, of course, always check. Here's how we might analyze tree3.lchild:

function largestInTree(tree) {  // tree3.lchild
    if( typeof tree === "number" ) {
        // a leaf, so trivially the leaf is the largest value
        return tree;
    } else {
        // recursively compute largest in each subtree
        let largestLeft  = largestInTree(tree.lchild); // f(tree3.lchild.lchild) returns 4
        let largestRight = largestInTree(tree.rchild); // f(tree3.lchild.rchild) returns 5
        return Math.max(largestLeft, largestRight); // returns 5
    }
}

We can invoke the function on these to see:

largestInTree(tree3.lchild); // 5
largestInTree(tree3.lchild.lchild); // 4
largestInTree(tree3.lchild.rchild); // 5

You can invoke the function on any node in any of the trees to see what it returns.

Notice that the largestInTree function does not use or set any global variables. In fact, global variables are usually pernicious for recursive functions, since every recursive call presumably will need to use the same global variable. In general, you should avoid global variables with recursive functions. Your code should be purely functional, which means that the function's value depends only on its argument (which tree node it's called on).

Functions like these that operate on a tree and return some useful computation on them are easy to write once you get the hang of it. We'll do some in class.

Now let's turn to more complicated computations.

Display Tree¶

Suppose we want to convert our random tree into elements in the DOM. Each node will be drawn with a box around it and a little left padding so it'll be indented:

.node {
    border: 1px solid black;
    padding-left: 2em;
}

.leaf {
    border: 1px solid red;
    padding-left: 2em;
}

The idea will be to generate a DOM element as the return value from the recursive JS function. Leaves will return p elements, and nodes will return div elements. Like our largestInTree function, this recursive function will just operate on a single tree node and will return an unattached DOM element.

However, we will also need a "driver" function that will start the recursion at the top (root) of the tree and receive the finished DOM element and attach it to the tree.

The driver will start the function on the root, get the DOM element for the entire tree, and then attach the whole thing to the DOM someplace, namely a static DIV whose id is tree_display.

Here's the JS:

// purely functional recursive function
function makeTree(node) {
    if( typeof node == "number" ) {
        return $("<p>").addClass("leaf").text(node);
    } else {
        var parentDiv = $("<div>").addClass("node");
        parentDiv.append(makeTree(node.lchild));
        parentDiv.append(makeTree(node.rchild));
        return parentDiv;
    }
}

// "driver" function
function showRandomTree(probLeaf) {
    var tree = randTree(probLeaf);
    var dom_elt = makeTree(tree);
    $("#tree_display").empty().append(dom_elt);
}

Try makeTree and showRandomTree in the JS console and play around with it a bit so that you feel confident with it.

Finally, let's make a slider for probability values and a button to allow us to try this many times:

<label>probLeaf: 
    <input type="range" id="probLeaf" name="probLeaf" min="0.5" max="0.6" step="0.01">
</label>
<p>chosen probability: <output id="probLeaf_display" for="probLeaf"></output></p>
<button id="new_tree">Make a Tree</button>
<div id="tree_display">tree goes here</div>

Aside: I've used an output HTML element. This is an element that can be used to display dynamic values in a way that is more accessible than just SPAN. Here, it displays the numeric value of the slider

And the JavaScript

$("#probLeaf").on('change', function () {
       var prob = $('[name="probLeaf"]').val();
       $("#probLeaf_display").text(prob);
});

$("#new_tree").on('click',
    function () { 
       var prob = $('[name="probLeaf"]').val();
       showRandomTree(prob);
    });

Summary¶

What we have done here is match some recursive algorithms with a recursive data structure, namely a binary tree:

• randTree generates a random binary tree by growing it from the root, where each node is either a number from 1-100 or a binary node, with a random binary tree for each child. That is, each child is generated by the same algorithm that generates the tree itself. The base case (the leaves of the tree) are the random numbers from 1-100. The recursive case (the nodes of the tree) are the nodes with two children.
• showRandomTree converts a random binary tree like the ones returned by randTree into some DOM nodes to display it. The leaves are displayed with paragraph elements containing the number from 1-100. The nodes are displayed with DIV elements that contain, recursively, the DOM elements displaying the left child and the right child.