Counting Height in Nodes Instead of Edges

A single node has height 0 when edges are counted, and 1 when nodes are.

The height of a tree is counted in one of two ways: in edges, the links from a parent to a child, or in nodes. This card covers the two conventions, why the same tree gets two answers one apart, and how to tell which convention a question or a library uses before comparing an answer with it.

The expectation is that height has one meaning, and it has two. Counting edges, a single node has height 0, because there is no link below it. Counting nodes, the same node has height 1. This subject counts edges, which gives an empty tree, one with no nodes at all, a height of -1: one node has height 0, and the empty tree is one less. Counting nodes gives the empty tree 0. In code, the two differ only in the base case, the answer for the empty tree, and the recursive step is the same. The listing computes both for every node of the tree used throughout this topic, with the two base cases highlighted.

height_conventions.pypy

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def height_in_edges(node):
    if node is None:
        return -1
    return 1 + max(height_in_edges(node.left), height_in_edges(node.right))


def height_in_nodes(node):
    if node is None:
        return 0
    return 1 + max(height_in_nodes(node.left), height_in_nodes(node.right))


def report(node, depth):
    if node is None:
        return
    print(f"node {node.value}: depth {depth}, height {height_in_edges(node)} in edges, {height_in_nodes(node)} in nodes")
    report(node.left, depth + 1)
    report(node.right, depth + 1)


root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6, Node(7))))
report(root, 0)
print("empty tree:", height_in_edges(None), "in edges,", height_in_nodes(None), "in nodes")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

node 1: depth 0, height 3 in edges, 4 in nodes
node 2: depth 1, height 1 in edges, 2 in nodes
node 4: depth 2, height 0 in edges, 1 in nodes
node 5: depth 2, height 0 in edges, 1 in nodes
node 3: depth 1, height 2 in edges, 3 in nodes
node 6: depth 2, height 1 in edges, 2 in nodes
node 7: depth 3, height 0 in edges, 1 in nodes
empty tree: -1 in edges, 0 in nodes

Every node's two heights differ by exactly one, and so do the empty tree's. The table takes four cases from the output.

One tree's heights under each convention, as the listing printed them
Tree	Height in edges	Height in nodes
The empty tree	-1	0
A single node, such as the leaf 4	0	1
Node 6 and its one child, 7	1	2
The whole tree, from the root 1	3	4

The mistake shows up as an answer that is off by one. A tree whose longest path from the root to a leaf passes through 4 nodes has height 3 in edges and 4 in nodes, and each is right under its own convention. Many textbooks count edges, while many coding exercises that ask for a tree's maximum depth count nodes, so an answer checked against the wrong one looks wrong when it is not.

Before comparing, find what the source says the height of a single node is. If it says 0, it counts edges; if it says 1, nodes. The empty tree confirms it: -1 means edges, and 0 means nodes. In your own code, pick one convention and let the name carry it, as height_in_edges does.

← → move through sections and cards