Trees and terminology

Written Explanation

What a tree is

A tree is a set of nodes joined by links (also called edges). Two rules define it:

1. There is exactly one starting node, the root, and every other node can be reached from it by exactly one path.
2. There are no cycles: you can never follow links and arrive back where you started.

An organization chart is the classic picture. The CEO is the root. Each person has one boss (their parent) and may have people reporting to them (their children).

Trees are usually drawn upside down, with the root at the top and the branches growing downward. That is only a drawing convention.

The vocabulary

Take this tree. The numbers are just labels inside the nodes.

        8
       / \
      3   10
     / \
    1   6

• The root is 8.
• 3 is the parent of 1 and 6; 1 and 6 are siblings.
• The leaves are 1, 6, and 10. The internal nodes are 8 and 3.
• The subtree rooted at 3 is the node 3 with 1 and 6 below it.
• The longest path is 8 to 3 to 1 (two links), so the height is 2.

Height counts links, not nodes. A tree with one node has height 0. Some books count nodes instead, so check which convention is in use. In this module, height means links.

Binary trees

A tree can have any number of children per node. A binary tree limits each node to at most two children, called the left child and the right child. Each side may also be empty. The drawing above is a binary tree.

In Java, a binary tree node needs a value and two references:

public class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }

    boolean isLeaf() {
        return left == null && right == null;
    }
}

A missing child is stored as null. A node is a leaf when both references are null. A reference to a whole tree is just a reference to its root node, and null stands for the empty tree.

Trees are recursive

Look again at the node 3 in the drawing: it is itself the root of a smaller tree. Every node is the root of its own subtree, and each subtree has the same shape as the whole. A binary tree is either empty, or a root with a left subtree and a right subtree, each of which is again a binary tree.

This is the same self-similar idea you used in recursion: solve the problem for the whole tree by solving it for the two subtrees, then combine the answers. The base case is the empty tree (null). Here is the height:

static int height(Node n) {
    if (n == null) return -1;
    return 1 + Math.max(height(n.left), height(n.right));
}

The base case returns -1 so that a single node, whose two children are null, gets 1 + max(-1, -1) = 0. This matches the counting-links convention. Most tree methods you will write look like this: if the node is null, return a base answer; otherwise combine the answers from the left and right subtrees.

Not every structure is a tree

If a node can be reached by two different paths, or a link leads back up to an ancestor, the structure is a graph, not a tree. A road map is a graph. Graphs get their own module later in the course.