Node Depths

Tags

Node Depths

Category

Binary Trees

Difficulty

Easy

Problem Statement

Given a binary tree, return the sum of the depths of all nodes. The depth of a node is its distance from the root. The root has depth 0, its children have depth 1, and so on.

Intuition

Each node contributes its own depth to the total sum. By traversing the tree and tracking the current depth, we simply accumulate each node's depth into a running total. This is a straightforward DFS or BFS traversal where we carry depth information along.

Approach

  1. Start a recursive DFS at the root with depth 0.
  2. If the node is null, return 0.
  3. Otherwise, return depth + nodeDepths(node.left, depth + 1) + nodeDepths(node.right, depth + 1).
  4. The recursion naturally sums up the depths across the entire tree.

Alternatively, use an iterative approach with a stack (DFS) or queue (BFS), storing (node, depth) pairs.

Pseudocode

function nodeDepths(root, depth = 0):
    if root is null:
        return 0
    return depth + nodeDepths(root.left, depth + 1) + nodeDepths(root.right, depth + 1)

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Every node is visited once.
  • Space: O(h) where h is the height of the tree, due to the recursive call stack. This is O(log n) for a balanced tree and O(n) for a skewed tree.

Key Insights

  • The problem reduces to a simple traversal with depth tracking.
  • Each node's contribution is independent — it simply adds its depth value.
  • The total sum for a complete binary tree of height h is: sum of d * (number of nodes at depth d) for d from 0 to h.
  • This can also be computed iteratively to avoid stack overflow on very deep trees.

Edge Cases

  • A tree with a single node: the sum is 0 (root has depth 0).
  • Null/empty tree: return 0.
  • Completely skewed tree (essentially a linked list): sum is 0 + 1 + 2 + ... + (n-1) = n*(n-1)/2.
  • All nodes on one side — the recursion should still work correctly as the null children return 0.

Linked mentions