Recursive Methods on a Binary Tree

A binary tree is built from Node objects. Each node holds a value and references to its left and right subtrees. A null reference is the empty tree:

public class Node<T> {
  public T value;
  public Node<T> left;
  public Node<T> right;

  public Node(T value) {
    this.value = value;
  }
}

Each method below is static, takes the root of a tree, and may be called on the empty tree. The height of a tree is the number of edges on the longest path from the root down to a leaf. The depth of a node is the number of edges on the path from the root down to that node.

Solution

public static <T> int size(Node<T> node) {
  if (node == null) {
    return 0;
  }
  return 1 + size(node.left) + size(node.right);
}

Solution

public static <T> int height(Node<T> node) {
  if (node == null) {
    return -1;
  }
  return 1 + Math.max(height(node.left), height(node.right));
}

The empty tree returns -1. A leaf has height 0, and both of its subtrees are empty, so 1 + max(height(empty), height(empty)) must equal 0. That forces height(empty) to be -1.

Solution

public static <T> int countLeaves(Node<T> node) {
  if (node == null) {
    return 0;
  }
  if (node.left == null && node.right == null) {
    return 1;
  }
  return countLeaves(node.left) + countLeaves(node.right);
}

Solution

Two leaves can have different depths, but both have the same two empty subtrees. A method that works only from the subtrees gives both leaves the same answer. Depth depends on the path above the node, not on what is below it.

Exercise

Node has no reference to its parent, so the depth of a node has to be found by searching down from the root. Write a recursive method that returns the number of edges from node down to target, or -1 if target is not in the tree rooted at node. Match target by reference, not by value. The depth of target in the whole tree is then depth(root, target).

public static <T> int depth(Node<T> node, Node<T> target) {
  // TODO
}

Solution

public static <T> int depth(Node<T> node, Node<T> target) {
  if (node == null) {
    return -1;
  }
  if (node == target) {
    return 0;
  }
  int left = depth(node.left, target);
  if (left != -1) {
    return 1 + left;
  }
  int right = depth(node.right, target);
  if (right != -1) {
    return 1 + right;
  }
  return -1;
}

Here is a binary tree:

          ╭───╮
          │ A │
          ╰─┬─╯
       ┌────┴────┐
     ╭─┴─╮     ╭─┴─╮
     │ B │     │ E │
     ╰─┬─╯     ╰───╯
    ┌──┴──┐
  ╭─┴─╮ ╭─┴─╮
  │ C │ │ D │
  ╰───╯ ╰───╯

Exercise

This version of depth combines the two subtree answers with Math.max, the way height does:

public static <T> int depth(Node<T> node, Node<T> target) {
  if (node == null) {
    return -1;
  }
  if (node == target) {
    return 0;
  }
  return 1 + Math.max(depth(node.left, target), depth(node.right, target));
}

What does depth(root, target) return on the tree above, where root is the node holding A and target is the node holding E? What goes wrong?

Solution

It returns 2, but the depth of E is 1. The leaves C and D do not contain the target, yet each returns 1 + max(-1, -1) = 0, which means “found here.” B then returns 1 + max(0, 0) = 1, and the root returns 1 + max(1, 0) = 2. The 1 + should apply only when a subtree found the target. A -1 has to be passed up unchanged.