Height in Trees

In the context of tree data structures, the concept of "height" is crucial for understanding the structure and efficiency of operations on trees. This page provides an overview, definition, examples, and implementation details related to the height of a tree.

Overview

The height of a tree is a measure of its depth, specifically the number of levels it contains, excluding the root. It is also used to describe individual elements within the tree, referring to the length of the longest path from an element to a leaf.

Definition

The height of a tree is defined as the number of segments in the longest path from the root to a leaf. For an empty tree, the height is defined as -1. This definition ensures that the height reflects the number of edges or segments, rather than the number of nodes, in the longest path.

Example

Consider the following example from Figure 10.2:

  • The first tree has a height of 2.
  • The second tree has a height of 3.
  • The third tree has a height of 6.

These examples illustrate how the height increases with the number of levels or segments in the tree.

Implementation

The height of a tree can be computed using a recursive method. Below is a listing of a method to calculate the height of a tree:

public int height() {
  return 1 + Math.max(left.height(), right.height());
}

This method works by recursively calculating the height of the left and right subtrees and returning 1 plus the maximum of these heights. This approach ensures that the height reflects the longest path from the root to a leaf.

Additional Listings

In the Tree class, methods to compute the size and height of a tree are defined as follows:

public abstract int size();
public abstract int height();

For an empty tree, the height method returns -1, as previously mentioned. The implementation of the height method in a non-empty tree (class T) returns 1 plus the maximum height of the two branches:

public int size() {
  return 1 + left.size() + right.size();
}

public int height() {
  return 1 + Math.max(left.height(), right.height());
}

This implementation highlights why the height of an empty tree is set to -1. If it were 0, the height would incorrectly represent the number of elements in the path rather than the number of segments.