Practice: Binary Tree Height

In this assignment, you'll work on the problem "Binary Tree Height."

Try to solve the problem independently, but feel free to reference the hints or walkthrough if you stop making progress.

Problem Description

// Given the root node of a binary tree, implement a
// function `getHeight` that calculates its height.

// The height of the tree is the level of the
// deepest node or the longest path from the root
// to a leaf node.

// The root node is considered to have a height of 1.

// Example

//      1
//     / \
//    2   3
//   / \
//  4   5


// The height of this binary tree is 3, as the
// longest path from the root node to a leaf node
// (either from 1 to 4 or from 1 to 5) involves 3 nodes.

class Node {
  constructor(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }
}

// Helper function for test cases
function buildTree(arr) {
  if (arr.length === 0) {
    return null;
  }

  const nodes = [];

  const val = arr.shift();
  const root = new Node(val);
  nodes.push(root);

  while (arr.length > 0) {
    const curr = nodes.shift();

    const leftVal = arr.shift();
    if (leftVal !== null) {
      curr.left = new Node(leftVal);
      nodes.push(curr.left);
    }

    if (arr.length > 0) {
      const rightVal = arr.shift();
      if (rightVal !== null) {
        curr.right = new Node(rightVal);
        nodes.push(curr.right);
      }
    }
  }

  return root;
}

// Test Cases

const tree1 = buildTree([1]);
console.log(getHeight(tree1) === 1);

const tree2 = buildTree([1, 2, 3, null, null, 4, 5]);
console.log(getHeight(tree2) === 3);

const tree3 = buildTree([1, 2, 3, 4, 5, 6, 7]);
console.log(getHeight(tree3) === 3);

const tree4 = buildTree([1, 2, 3, null, null, 4, 5, null, null, null, 6]);
console.log(getHeight(tree4) === 4);

const tree5 = buildTree([1, 2, null, 3, null, 4, null, 5, 6, null, null, null, 7]);
console.log(getHeight(tree5) === 6);

const tree6 = buildTree([1, 2, null, 3, null, 4, null, 5, null, 6, 8, null, 7, null, 9, null, null, null, 10]);
console.log(getHeight(tree6) === 8);
// All test cases should log true

Walkthrough & Solution

Try to solve the problem using recursion. To use recursion, start by defining your base case and recursive definition.

Here is the updated recursive definition template for this problem:

The [problem description] of the [data structure] is [1] or [value of element], [operation] the [min/max/comparison] between the left and right subtrees of the [data structure].

Let's start with two examples to visualize the tree height for different trees:

To solve this problem, like in all recursive solutions, we'll define a base case and a recursive definition.

Base Case

In this problem, like in many others dealing with binary trees, the base case occurs when the node is null. Since we are trying to find the maximum depth, which is an integer, we need to return an integer when the node is null.

The node that is null doesn't have any height (its height is zero). We can return 0 in this case.

Base Case: If the node is null, return 0.

Recursive Definition

Remember our recursive definition template from this assignment. We'll have to update it slightly to include the calculation. Here is the modified template.

The [problem description] of the [data structure] is [1] or [value of element], [operation] the [min/max/comparison] between the left and right subtrees of the [data structure].

Let's break down each part enclosed in square brackets:

[problem description]: Height
[data structure]: Binary Tree
[1] or [value of element]: This means in some subproblems we'll be adding the number 1 and sometimes the value of the node.
[operation]: This can be "+", "-" etc.
[min/max/comparison]: This means that we are taking either the minimum, maximum, or, for example, comparing the height of the left subtree and the height of the right subtree.

If we fill in the template, we get:

Recursive Definition: The height of the binary tree is 1 plus the maximum between the height of the left subtree and the height of the right subtree.

Let's explain this further by creating a tree step-by-step:

Step 1: Initially, we have only one node, so the result is one plus the maximum between the height of the left subtree and the height of the right subtree. Since there are no children nodes, the height of the left and right subtrees are both zero.

Step 2: Once we add a node on the right, the result becomes 1 plus the maximum between the height of the left subtree (0) and the height of the right subtree (1), which adds up to 2.

Step 3: When we add another node on the right, the result becomes 1 plus the maximum between the maximum depth of the left subtree (0) and the maximum depth of the right subtree (2), which adds up to 3.

Step 4: If we add another node to the left of node 3, the result remains 3 since the maximum depth of the binary tree with the root 3 hasn't changed and it's still 2. This is the node itself plus the maximum between the maximum depth of its left subtree (1) and the maximum depth of its right subtree (1).

Step 5: Finally, if we add a node to the left of node 1, the result won't change. The maximum depth of the left subtree with node 2 as the root is less than the maximum depth of the right subtree with node 3 as the root.

Let's see the code implementation:

function getHeight(root) {
  if (root === null) {
    return 0
  }

  return 1 + Math.max(getHeight(root.left), getHeight(root.right))
}

As is evident by this solution, much more work goes into defining a base case and understanding the recursive step than writing code.