Measuring Depth

The depth of a node is the number of edges on the path from the root down to that node. Here is our tree again:

       ╭───╮
       │ 3 │
       ╰─┬─╯
    ┌────┴─────┐
  ╭─┴─╮      ╭─┴─╮
  │ 5 │      │ 8 │
  ╰─┬─╯      ╰───╯
  ┌─┘
╭─┴─╮
│ 1 │
╰───╯

The root 3 has depth 0, since there are no edges between the root and itself. Its children 5 and 8 have depth 1. The leaf 1 is two edges below the root, so it has depth 2.

Height and depth both count edges, but they count them in opposite directions. The height of a node is measured down from the node to the deepest leaf below it. The depth of a node is measured from the root down to the node. Here are both values for each node in our tree:

• 3 has height 2 and depth 0.
• 5 has height 1 and depth 1.
• 8 has height 0 and depth 1.
• 1 has height 0 and depth 2.

Computing depth from the subtrees

We wrote size and height the same way: handle the empty tree, then build a node’s answer out of the answers from its two subtrees. So the natural first try is to do the same for depth, and write depth(node) using depth(node.left) and depth(node.right).

Look at the leaves 8 and 1. Both have two empty subtrees, so their subtrees are exactly the same. Whatever depth computes from the subtrees, it computes the same thing for 8 and for 1. But 8 has depth 1 and 1 has depth 2. So no method can get the depth of a node from its subtrees alone.

This is the difference between height and depth. The height of a node depends only on what is below the node. The depth of a node depends only on what is above it: the path that leads from the root down to it.

Computing depth from the parent

If the depth comes from above, then let’s look above. A node is one edge below its parent, so its depth is one more than its parent’s depth:

depth(node) = 1 + depth(parent)

The base case is the root, which has no parent and has depth 0. This is the height recurrence turned upside down, and it is correct. For 1, the depth is one more than the depth of 5, which is one more than the depth of 3, which is 0. That gives 2.

But we cannot write this against our Node, which only has a left and a right reference. It has no reference to its parent. From a node, we can only move down.

Searching down from the root

Since we can only move down, we have to start at the root and walk down until we reach the node we want. That changes what the method needs. It needs the root, where the walk starts, and the node whose depth we want. We call that node target. So depth(node, target) returns the number of edges from node down to target.

Notice that this measures from node, whatever node we pass in, not from the root of the whole tree. That is what lets us think recursively, the same way we did for size. The target is either node itself, or somewhere in the left subtree, or somewhere in the right subtree.

If node is the target, the answer is 0. There are no edges between a node and itself.

Otherwise, suppose the target is in the left subtree, and suppose depth(node.left, target) already returns the correct answer: the number of edges from node.left down to the target. node is one edge above node.left, so the target is one more edge below node. For example, 1 is one edge below 5, so depth(5, one) is 1. Then depth(3, one) is 1 + 1 = 2.

There is a catch. A node does not tell us which of its subtrees holds the target, so we have to ask both. At most one of them contains the target, and maybe neither does. So a call needs a way to say “the target is not in this subtree.” A depth is never negative, so we use -1 for that. This also gives the base case: the empty tree does not contain the target, so depth(null, target) is -1.

Trying the height approach

So each call gets two answers back, one from each subtree, the same as in height. height kept the larger of the two, and that looks like it works here too. The subtree that does not contain the target returns -1, which is smaller than any real depth, so max should pick the subtree that found it:

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));
}

Let’s try it on our tree with eight, the node holding 8, as the target. The answer should be 1.

1. depth(1, eight): 1 is not the target. Both of its subtrees are empty, so both calls return -1, and it returns 1 + max(-1, -1) = 0.
2. depth(5, eight): its left call returned 0 and its right call, on the empty tree, returns -1. It returns 1 + max(0, -1) = 1.
3. depth(8, eight): this is the target, so it returns 0.
4. depth(3, eight): it returns 1 + max(1, 0) = 2.

We get 2, not 1. So what went wrong? Look at step 1. The leaf 1 does not contain the target, so it should return -1. Both of its subtrees said “not here”, but adding one turned that -1 into 0, and 0 means “the target is this node.” Then 5 added one to that and claimed the target is one edge below it. At the root, max picked this wrong answer over the right one because it was larger.

The 1 + is only correct when the subtree actually found the target. When a subtree returns -1, we have to pass the -1 along and not add one to it.

Checking for -1

So we check each answer before we add one to it:

public static <T> int depth(Node<T> node, Node<T> target) {
  if (node == null) {
    return -1;  // the empty tree does not contain the target
  }
  if (node == target) {
    return 0;  // the target is this node
  }
  int left = depth(node.left, target);
  if (left != -1) {
    return 1 + left;  // found in the left subtree, one edge below this node
  }
  int right = depth(node.right, target);
  if (right != -1) {
    return 1 + right;  // found in the right subtree, one edge below this node
  }
  return -1;  // the target is in neither subtree
}

To find the depth of a node in the whole tree, you call depth(root, target).

The check node == target compares references. We are looking for that exact Node object, not for a node that holds the same value.

Let’s run depth(root, eight) again:

1. depth(3, eight): 3 is not the target, so it searches its left subtree.
2. depth(5, eight): 5 is not the target, so it searches its left subtree.
3. depth(1, eight): 1 is not the target. Both of its subtrees are empty and return -1, so it returns -1.
4. Back in depth(5, eight), left is -1, so it searches its right subtree. That is empty and returns -1, so 5 returns -1 as well.
5. Back in depth(3, eight), left is -1, so it searches its right subtree. depth(8, eight) finds the target and returns 0. right is 0, so 3 returns 1 + 0 = 1.

This time the answer is 1. The -1 from the leaf 1 reached the root unchanged.

The method also stops early. If the left search finds the target, the right subtree is never searched. depth(root, one) finds 1 on the left and never looks at 8. If the target is not in the tree, every search returns -1, so the method visits every node and returns -1.

Compare this with height. Both measure down from the node they are given, and both build the answer on the way back up: the target returns 0, and each call above it adds one. The difference is in how the two subtree answers are combined. height uses both and keeps the larger. depth uses the one subtree that contains the target, and passes -1 up unchanged when neither does.