Course contentsShow
← Computer Science
Lesson 490 of 2,87211. Binary TreesFree lesson

Path Length Properties

Internal and external path length definitions and their role in analyzing tree performance.

Path Length Properties

You'll learn how to measure the total "distance" from the root to all nodes in a binary tree and why this metric matters for tree performance.

What Is Path Length?

Recall that a path is the sequence of edges from one node to another. The path length to a node is the number of edges you traverse from the root to reach it — which is exactly the node's depth.

Now we aggregate across the entire tree:

Internal Path Length (IPL)

The internal path length is the sum of the depths of all internal nodes (non-leaves).

For example, if internal nodes are at depths 0, 1, 1, 2, 2, then IPL = 0 + 1 + 1 + 2 + 2 = 6.

External Path Length (EPL)

The external path length is the sum of the depths of all external nodes (leaves or null children).

Think of external nodes as the "empty spots" where children could be but aren't. In a complete tree with 3 leaves at depth 2, EPL = 2 + 2 + 2 = 6.

Why It Matters

Path lengths measure the average search cost in a tree. A smaller IPL means nodes are closer to the root on average, resulting in faster searches, insertions, and traversals.

  • Balanced trees have low IPL because nodes are spread evenly across fewer levels.
  • Unbalanced trees (like a chain) have high IPL because most nodes are far from the root.

Path length also helps analyze tree algorithms: many operations' time complexity is proportional to IPL divided by the number of nodes.

Key Takeaway:
Internal and external path lengths quantify how "spread out" a tree is; lower path lengths mean better average-case performance for most tree operations.