JSFeeds: zsoltnagy.eu - Binary Trees, Recursion, Tail Call Optimization in JavaScript

Thursday, 18 January, 2018 UTC

Binary Trees, Recursion, Tail Call Optimization in JavaScript

Summary

You might not know about me that I have conducted tech interviews with over 500 software developers from more than twenty countries with the objective of identifying and hiring the best talent. I have also been in the candidate position, interviewing for positions ranging from junior developer to CTO.

In this series, I am exposing the secrets of JavaScript interviewing. You will get a chance to solve a tech interview exercise every single week. You will not only refresh your JavaScript skills, but above all, you will learn the mindset required for solving interview exercises. We will start with simple tasks, and then transition to complex exercises that you could even use to build your portfolio.

We are covering each aspect of the job interviewing process. You have already seen some theoretical questions that demonstrate how well you can use JavaScript. You have seen some coding challenges that not only let you showcase your problem solving abilities, but they also demonstrate your theoretical knowledge, let alone your algorithmic skills. You are yet to experience some longer homework assignment type of tasks that challenge your abilities to write maintainable software. Some of these challenges are timed, some require you to use some frameworks or libraries, while others require you to structure your code.

The challenge I have chosen for this session is an online coding challenge on a site called HackerRank.

I have already recommended that you go through the challenges of a similar site called Codility. HackerRank ups the ante a bit more by giving you challenges of continuously increasing difficulty.

Once you sign up, HackerRank recommends a thirty day challenge for you. You get one exercise a day, which often takes just a couple of minutes. The thirty day challenge is very healthy, because if builds a habit of coding just a bit every single day.

Consider the option of using challenges like the ones HackerRank provides to improve your problem solving skills.

As an illustration, I will now solve a coding challenge that can be found in the Data Structures section of HackerRank. The challenge is called Height of a Binary Tree.

For advanced positions, you will be expected to know some data structures and algorithms, as well as some programming techniques like pure functional programming and recursion. We will build on some of this knowledge.

You can either read the task by signing up on HackerRank and visiting the link, or by reading my summary here:

Suppose a binary tree is given with root R. Each node may be connected to zero, one, or two child nodes. The edges of the tree are directed from the parent nodes towards child nodes. Determine the height of the tree, defined as the maximal number of edges from R to any node in the tree.

The JavaScript data structure of a node is as follows:

// type Node = { data: number, left: Node | null, right: Node | null }

Solution:

Let’s sketch a plan:

the height of a tree with one node with no children is 0
the height of a tree with a left and a right subtree is 1 plus the maximum of the height of the left subtree and the right subtree

These are all the ideas you need to demonstrate to be able to solve this exercise. Let’s create a solution function.

const treeHeight = tree =>
    Math.max(
        tree.left === null ? 0 : 1 + treeHeight( tree.left ),
        tree.right === null ? 0 : 1 + treeHeight( tree.right )
    );

That’s it. We have solved this exercise with recursion.

Notice the solution is purely functional, as it is not relying on any side-effects. Also notice the elegance of the solution in a sense that we just described the input (tree) and the return value.

Now, your interviewer may ask you to solve this exercise without recursion. Remember, for every recursive solution, there exists an equivalent iterative solution. In order to find the iterative solution, we need to save the upcoming recursive calls in a queue-like data structure (a simple array will do), and introduce some accumulator variables that store the current state of the computation.

Let’s start writing the frame of substituting recursion:

const treeHeight = root => {
    let nodes = [{ root, distance: 0 }];
    let maxHeight = 0;

    while ( nodes.length > 0 ) {
        let node = nodes.pop();
        // ...
    }
}

We put the tree in a data structure where we save the distance from the root. We also initialize the maximum height of the tree to zero.

Instead of recursion, we have a while loop. As long as there are nodes in the nodes array, we pop one, and process its consequences. During the processing, we may push more nodes to the array:

const treeHeight = root => {
    let nodes = [{ node: root, distance: 0 }];
    let maxHeight = 0;

    while ( nodes.length > 0 ) {
        let currentTree = nodes.pop();
        maxHeight = Math.max( maxHeight, currentTree.distance );
        if ( currentTree.node.left !== null ) {
            nodes.push( {
                node: currentTree.node.left,
                distance: currentTree.distance + 1
            } );
        }
        if ( currentTree.node.right !== null ) {
            nodes.push( {
                node: currentTree.node.right,
                distance: currentTree.distance + 1
            } );
        }        
    }

    return maxHeight;
}

Now that you have completed the iterative solution, a common question is whether you can write a recursive solution that is tail call optimized. Let’s see the original recursive solution:

const treeHeight = tree =>
    Math.max(
        tree.left === null ? 0 : 1 + treeHeight( tree.left ),
        tree.right === null ? 0 : 1 + treeHeight( tree.right )
    );

The recursive calls are inside Math.max, so they are not in tail position. We have to extract them out from the Math.max. The question is how.

The iterative solution always gives you an idea for tail recursion. Even if you are unsure about the exact definition of tail position for recursive function calls, you can just take the state space of the iterative function, implement the while loop using recursion:

const treeHeight = root =>
    treeHeightRecursive( [{ node: root, distance: 0}], 0 );

const treeHeightRecursive = ( nodes, maxHeight ) => {
    let currentTree = nodes.pop();
    maxHeight = Math.max( maxHeight, currentTree.distance );  
    if ( currentTree.node.left !== null ) {
        nodes.push( {
            node: currentTree.node.left,
            distance: currentTree.distance + 1
        } );
    }
    if ( currentTree.node.right !== null ) {
        nodes.push( {
            node: currentTree.node.right,
            distance: currentTree.distance + 1
        } );
    } 
    if ( nodes.length === 0 ) return maxHeight;
    return treeHeightRecursive( nodes, maxHeight );       
}

One minor difference with respect to the iterative solution is that we have to manually create an exit condition from recursion with the nodes.length === 0 condition.

If you want to access more exercises, or you wish to fine-tune your JavaScript skills, consider taking a look at ES6 in Practice.

Now that we have solved this exercise together, don’t forget that there are four pillars for a successful tech interview:

Tech skills
Problem solving skills
Soft skills
Personal Branding

This blog addresses the first two skills. My other blog, devcareermastery.com addresses soft-skills, and my book The Developer’s Edge – How to Double Your Career Speed with Soft-Skills helps you with soft-skills as well as with your personal brand.

If you are interested in fine-tuning your JavaScript skills as well as your soft skills, I highly recommend that you consider purchasing The JavaScript Developer’s Career Bundle. This bundle contains my book ES6 in Practice, 4.5 hours of JavaScript videos, and The Developer’s Edge. You will not only be fully up-to-date with the latest version of JavaScript, but you will also learn how to build a fulfilling career for yourself.

Learn ES6 in Practice

... more @ zsoltnagy.eu

zsoltnagy.eu