Tree properties: depth, height and size

A tree’s shape often determines an algorithm’s cost. A short, balanced tree allows operations to descend a few levels; a long, chain-shaped tree can force a search through almost all nodes.

Define the measurement

For a root at depth 0, each child has depth one more than its parent. The tree height is the maximum depth of any leaf, measured in edges. A single-node tree has height 0 under this convention; the empty tree is sometimes assigned height -1, but you must state that convention explicitly.

The size counts nodes. For a non-empty finite rooted tree, there are size - 1 edges. That identity alone does not establish that a graph is a tree: you must also ensure connectivity and no cycles.

Worked example

Suppose R has children A and B, A has C, and C has D. The depths are R=0, A=1, B=1, C=2, D=3. Tree height is 3; size is 5; edges are 4. The tree is not balanced around R because the left side extends much further down.

Computing height

A recursive height routine asks for the heights of its children. A leaf contributes zero edges; other nodes contribute one plus the greatest child height. The following binary-tree example measures edge height, with the empty subtree convention of -1.

C#

C# | Height.cs

using System.Collections.Generic;

public sealed class Node
{
    public int Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
    public Node(int value) => Value = value;
}

static int Height(Node? node) => node is null ? -1 :
    1 + Math.Max(Height(node.Left), Height(node.Right));

C++

C++ | Height.cpp

#include <memory>
#include <vector>

struct Node {
    int value;
    std::unique_ptr<Node> left, right;
    explicit Node(int value) : value(value) {}
};

#include <algorithm>
int height(const Node* node) {
    if (!node) return -1;
    return 1 + std::max(height(node->left.get()), height(node->right.get()));
}

The routine visits every node once, so its time is O(n). Its recursive call stack uses O(h) additional memory for tree height h in nodes or edges up to a constant difference; a path-shaped tree needs O(n) stack depth. The input tree storage is excluded from this auxiliary measure.

Beware of ambiguous claims

Height and depth are different for interior nodes. A perfectly balanced binary tree has height O(log n), but a general binary tree is not necessarily balanced. Never infer logarithmic performance from the word binary alone.

Continue with binary tree shapes and tree traversals.