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

Calculating Tree Metrics

Algorithms to compute height, node counts, and balance factors through recursive tree traversal.

Calculating Tree Metrics

You'll learn how to write recursive algorithms that measure important properties of binary trees like height, node counts, and balance factors.

The Core Idea

Think of a tree metric as a measurement that describes some property of your tree structure. Just as you might measure a physical tree's height from ground to tallest branch, we measure binary tree properties by breaking the problem into smaller subproblems — the essence of recursion. Each metric follows a pattern: compute the metric for left and right subtrees, then combine those results to get the parent's metric.

Common Tree Metrics

Height Calculation

The height of a tree is the longest path from root to any leaf. Recursively: the height of a node is 1 + max(left_height, right_height). A null node has height -1 (or 0, depending on convention).

Node Count

The total node count is straightforward: count yourself (1), plus all nodes in your left subtree, plus all nodes in your right subtree. Base case: a null node contributes 0.

Balance Factor

The balance factor of a node measures how balanced its subtrees are: height(left) - height(right). A balanced tree keeps this value between -1 and 1 for every node. This metric combines two calculations: you need the height of both subtrees to compute balance.

The Recursive Pattern

All these metrics follow the same template:

  1. Base case: What's the value for an empty tree?
  2. Recursive step: Calculate metric for left and right subtrees
  3. Combine: Merge the subresults using addition, max, subtraction, etc.

This pattern makes tree algorithms elegant but requires understanding that each recursive call operates on progressively smaller subtrees until hitting base cases.

Key Takeaway: Tree metrics are computed recursively by solving for subtrees first, then combining results—height uses max, count uses sum, and balance uses subtraction of heights.