Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Height & Diameter
DSA

Height & Diameter

Learn how recursive tree properties can be used to calculate height and diameter efficiently.

Tree Height and Diameter are post-order DFS patterns where each node returns information about its subtree upward.

Its core advantage:

A single DFS pass computes per-subtree metrics — combine children’s results to get the parent’s answer.

Focus on recognizing:

“Height” + “Depth” + “Longest path” + “Maximum distance” = Height / Diameter

Pattern Table

PatternTypical QuestionsTrigger
HeightMax depth from rootCount edges/nodes to leaf
DiameterLongest path between nodesLeft height + right height
Max DepthMaximum depth of treeDFS returning depth

Mental Trigger

Post-order: children return their height → parent combines them → answer bubbles up.

1. Generic Java Height / Diameter Template (Base)

public int height(TreeNode root) {
    if (root == null) return 0;

    int left = height(root.left);
    int right = height(root.right);

    return Math.max(left, right) + 1;
}
def height(root):
    if root is None:
        return 0

    left = height(root.left)
    right = height(root.right)

    return max(left, right) + 1
int height(TreeNode* root) {
    if (root == nullptr) return 0;

    int left = height(root->left);
    int right = height(root->right);

    return max(left, right) + 1;
}
function height(root) {
  if (root === null) return 0;

  const left = height(root.left);
  const right = height(root.right);

  return Math.max(left, right) + 1;
}

Everything else in Height / Diameter is just a modification of this template.

Pattern 1: Diameter of Binary Tree

Every node is a potential bend: leftDepth + rightDepth, take the max. Press ▶ to animate.

Diameter Of A Binary Tree

Find the longest path between any two nodes, measured in edges.

At each node, depth = 1 + max(child depths) and a candidate path = leftDepth + rightDepth. Track the max candidate as depths bubble up.

TREE VISUALIZER
Steps –
1220157
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        depth(node) = 0 if null
                      
                        2
                          else 1 + max(depth(L), depth(R))
                      
                        3
                        at each node: candidate = dL + dR
                      
                        4
                        answer = max over all candidates

Java Code

public int diameterOfBinaryTree(TreeNode root) {
    int[] max = {0};
    height(root, max);
    return max[0];
}

private int height(TreeNode root, int[] max) {
    if (root == null) return 0;

    int left = height(root.left, max);
    int right = height(root.right, max);

    max[0] = Math.max(max[0], left + right);

    return Math.max(left, right) + 1;
}
def diameter_of_binary_tree(root):
    max_diameter = [0]
    height(root, max_diameter)
    return max_diameter[0]

def height(root, max_diameter):
    if root is None:
        return 0

    left = height(root.left, max_diameter)
    right = height(root.right, max_diameter)

    max_diameter[0] = max(max_diameter[0], left + right)

    return max(left, right) + 1
int diameterOfBinaryTree(TreeNode* root) {
    int maxDiameter = 0;
    height(root, maxDiameter);
    return maxDiameter;
}

int height(TreeNode* root, int& maxDiameter) {
    if (root == nullptr) return 0;

    int left = height(root->left, maxDiameter);
    int right = height(root->right, maxDiameter);

    maxDiameter = max(maxDiameter, left + right);

    return max(left, right) + 1;
}
function diameterOfBinaryTree(root) {
  const max = [0];
  height(root, max);
  return max[0];
}

function height(root, max) {
  if (root === null) return 0;

  const left = height(root.left, max);
  const right = height(root.right, max);

  max[0] = Math.max(max[0], left + right);

  return Math.max(left, right) + 1;
}

What Changed from the Base Template?

Track max across all nodes

Base:

return Math.max(left, right) + 1; // just return height

Added:

int[] max = {0};
max[0] = Math.max(max[0], left + right);

because diameter is the maximum of (left height + right height) across all nodes.

Height function doubles as diameter tracker

Base:

// returns height only

Changed:

// returns height AND updates max diameter
max[0] = Math.max(max[0], left + right);
return Math.max(left, right) + 1;

using a side effect in the height function to avoid a second traversal.

Diameter = Height function + Track max(left + right) across all nodes.

Pattern 2: Maximum Depth of N-ary Tree

Same recursion, but max runs over the whole children list. Press ▶ to animate.

Maximum Depth Of N-ary Tree

Find the deepest level of an N-ary tree (each node may have many children).

Depth = 1 + max over ALL children (a loop, not just two). The root takes the max across its children, not the sum — everything else mirrors the binary version. BFS level-counting is an equivalent zero-recursion alternative.

TREE VISUALIZER
Steps –
ABCDE
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        depth(node):
                      
                        2
                          if no children → 1
                      
                        3
                          return 1 + max over children
                      
                        4
                        answer = depth(root)

Java Code

public int maxDepth(Node root) {
    if (root == null) return 0;

    int maxChild = 0;

    for (Node child : root.children)
        maxChild = Math.max(maxChild, maxDepth(child));

    return maxChild + 1;
}
def max_depth(root):
    if root is None:
        return 0

    max_child = 0

    for child in root.children:
        max_child = max(max_child, max_depth(child))

    return max_child + 1
int maxDepth(Node* root) {
    if (root == nullptr) return 0;

    int maxChild = 0;

    for (Node* child : root->children)
        maxChild = max(maxChild, maxDepth(child));

    return maxChild + 1;
}
function maxDepth(root) {
  if (root === null) return 0;

  let maxChild = 0;

  for (const child of root.children)
    maxChild = Math.max(maxChild, maxDepth(child));

  return maxChild + 1;
}

What Changed from the Base Template?

Iterate over children list instead of left/right

Base:

int left = height(root.left);
int right = height(root.right);

Changed:

for (Node child : root.children)
    maxChild = Math.max(maxChild, maxDepth(child));

because N-ary trees have an arbitrary number of children, not just two.

N-ary Depth = Base Height + Loop over children instead of left/right.

Height / Diameter Pattern Evolution

Tree Height (return max child + 1)
    ↓
Diameter
    (+ track max(left + right) as side effect)
    ↓
N-ary Max Depth
    (+ loop over children list)

Common Mistakes

Returning 0 for null vs -1.

Edges-count: return -1 for null. Nodes-count: return 0 for null. Be consistent.

Confusing diameter definition.

Diameter is the number of edges on the longest path, NOT the number of nodes.

Using pre-order instead of post-order.

Height requires children’s results first — must be post-order.

Recognition Cheat Sheet

If you see…Think…
Height / depth of treePost-order return max + 1
Longest path between nodesHeight + track left + right
N-ary tree depthLoop over children
Balanced tree checkHeight + compare left vs right

My Private Notes

Notes are auto-saved locally to this device.