Tree Height, Depth & Diameter: Measuring a Tree

Two numbers describe where a node sits and how big a tree is: depth (distance from the root down to a node) and height (distance from a node down to its deepest leaf). The whole tree’s height — equal to its maximum depth — determines the cost of every operation. This page shows how to compute height, depth, and the related diameter, all in O(n).

These definitions were introduced in the trees introduction; here we compute them. We reuse the standard TreeNode.

Height of a tree

The height of a node is 1 + max(height of left, height of right), with an empty subtree contributing 0. (We measure height in edges; some texts count nodes, giving a result one larger — pick one convention and be consistent.)

int height(TreeNode* root) {
    if (root == nullptr) return 0; // empty subtree
    return 1 + std::max(height(root->left), height(root->right));
}

int height(TreeNode root) {
    if (root == null) return 0; // empty subtree
    return 1 + Math.max(height(root.left), height(root.right));
}

function height(root) {
  if (root === null) return 0; // empty subtree
  return 1 + Math.max(height(root.left), height(root.right));
}

def height(root):
    if root is None:
        return 0  # empty subtree
    return 1 + max(height(root.left), height(root.right))

Note on convention: This returns the node count of the longest root-to-leaf path (a single node → 1, empty → 0). To get the edge count, subtract 1. Many interview problems (“maximum depth of binary tree”) expect exactly this node-count form.

Depth of a specific node

The depth of a target value is how many edges separate it from the root. Walk down, counting steps, until you find it:

int depth(TreeNode* root, int target, int d = 0) {
    if (root == nullptr) return -1;        // not found
    if (root->val == target) return d;
    int left = depth(root->left, target, d + 1);
    if (left != -1) return left;
    return depth(root->right, target, d + 1);
}

int depth(TreeNode root, int target, int d) {
    if (root == null) return -1;           // not found
    if (root.val == target) return d;
    int left = depth(root.left, target, d + 1);
    if (left != -1) return left;
    return depth(root.right, target, d + 1);
}

function depth(root, target, d = 0) {
  if (root === null) return -1;            // not found
  if (root.val === target) return d;
  const left = depth(root.left, target, d + 1);
  if (left !== -1) return left;
  return depth(root.right, target, d + 1);
}

def depth(root, target, d=0):
    if root is None:
        return -1            # not found
    if root.val == target:
        return d
    left = depth(root.left, target, d + 1)
    if left != -1:
        return left
    return depth(root.right, target, d + 1)

Diameter: the longest path

The diameter of a tree is the number of edges on the longest path between any two nodes — it need not pass through the root. The trick: for each node, the longest path through it is leftHeight + rightHeight. Compute heights once and track the best, all in a single O(n) pass.

int diameterHelper(TreeNode* node, int& best) {
    if (node == nullptr) return 0;
    int l = diameterHelper(node->left, best);
    int r = diameterHelper(node->right, best);
    best = std::max(best, l + r);   // path through this node (in edges)
    return 1 + std::max(l, r);      // height in edges + 1
}
int diameter(TreeNode* root) {
    int best = 0;
    diameterHelper(root, best);
    return best;
}

int best;
int diameterHelper(TreeNode node) {
    if (node == null) return 0;
    int l = diameterHelper(node.left);
    int r = diameterHelper(node.right);
    best = Math.max(best, l + r);   // path through this node (in edges)
    return 1 + Math.max(l, r);
}
int diameter(TreeNode root) {
    best = 0;
    diameterHelper(root);
    return best;
}

function diameter(root) {
  let best = 0;
  function helper(node) {
    if (node === null) return 0;
    const l = helper(node.left);
    const r = helper(node.right);
    best = Math.max(best, l + r);   // path through this node (in edges)
    return 1 + Math.max(l, r);
  }
  helper(root);
  return best;
}

def diameter(root):
    best = 0
    def helper(node):
        nonlocal best
        if node is None:
            return 0
        l = helper(node.left)
        r = helper(node.right)
        best = max(best, l + r)   # path through this node (in edges)
        return 1 + max(l, r)
    helper(root)
    return best

For beginners: The diameter counts edges, so two leaves on opposite sides of the root in a 3-node tree have a diameter of 2.

Complexity

Quantity	Time	Space
Height	O(n)	O(h) recursion
Depth of a node	O(n)	O(h) recursion
Diameter	O(n)	O(h) recursion

A naive diameter that recomputes height at every node is O(n²) — the single-pass version above avoids that by returning the height and updating the best diameter together.

Going deeper: Height directly governs cost: every BST operation is O(h), which is why balanced trees work so hard to keep h = O(log n).

Next steps

Apply path reasoning to the lowest common ancestor problem, or practice on the tree exercises.