Diameter of Binary Tree

Diameter of Binary Tree looks like it is about one straight path. But the trick is that the longest path may not pass through the root at all. The interviewer wants to see if you can measure something at every node while you walk the tree just once.

🎯 The Problem

You get a binary tree and must find the length of the longest path between any two nodes.

The rules:

• A binary tree is a structure where each node has a value and up to two children.
• The length is counted in edges, which are the links between nodes, not the nodes themselves.
• The path does not have to go through the root. It can sit anywhere in the tree.
• It is just the longest chain of connected nodes you can draw.

Input:
       1
      / \
     2   3
    / \
   4   5

Output: 3

Explanation: The longest path is 4 -> 2 -> 5 ... 3, that is 4-2-1-3, which has 3 edges.

Here is the tree. The longest path runs from a leaf on the left, up through the root, and down to node 3.

🐢 Approach 1: Height at Every Node (Brute Force)

The idea in one line: at each node measure left height plus right height, and keep the biggest sum.

The idea:

• The longest path that bends at a node is its left height plus its right height.
• The height of a part is the number of edges down to its deepest leaf.
• The biggest such sum over all nodes is the diameter.

How it works:

• For every node, compute the left height and the right height.
• Add them. That is the path bending at this node.
• Keep the largest sum you ever see.

Why it is weak:

• To get the height at each node you walk that whole subtree again.
• So you compute heights over and over for the same nodes.
• On a long thin tree this reaches O(n²) time.

Here is the height-at-every-node code:

def diameter_of_binary_tree(root):
    def height(node):
        if not node: return 0
        return 1 + max(height(node.left), height(node.right))
    if not root: return 0
    through = height(root.left) + height(root.right)
    return max(through, diameter_of_binary_tree(root.left), diameter_of_binary_tree(root.right))

⚡ Approach 2: Measure Diameter While Measuring Height (Best)

The idea in one line: computing height already walks the whole subtree, so record the diameter during that same walk.

The idea:

• Write one recursive function that returns the height of a node.
• A recursive function is one that calls itself on smaller parts.
• While it computes height, it also tracks the largest left-plus-right sum it has seen.

How it works:

• The function returns height upward to the parent.
• As a side effect, it updates a shared best with left height plus right height at each node.
• When the walk finishes, that stored best is the answer.

Why it is fast:

• One walk does both jobs, so each node is visited once. That is O(n).
• Keep them separate in your head. Height is returned to the parent. Diameter is tracked on the side.

The diagram below shows the height each node returns, and how the diameter is the largest left-plus-right sum.

Steps to Solve

1. Keep a shared variable best that starts at 0.
2. Write a recursive height(node) function.
3. If the node is empty, return a height of -1, so a single node gives height 0.
4. Get the left height and the right height by recursion.
5. Update best with left height plus right height plus 2, the edges through this node.
6. Return the larger of the two child heights plus 1.
7. After the walk, best holds the diameter.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

Node *newNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int best = 0;

int max(int a, int b) { return a > b ? a : b; }

// returns height in edges; -1 for empty so a leaf is height 0
int height(Node *node) {
    if (node == NULL) return -1;
    int lh = height(node->left);            // left height
    int rh = height(node->right);           // right height
    int through = lh + rh + 2;              // edges of path bending here
    if (through > best) best = through;     // keep the largest
    return max(lh, rh) + 1;                 // height for the parent
}

int diameter(Node *root) {
    best = 0;
    height(root);
    return best;
}

int main(void) {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("%d\n", diameter(root));
    return 0;
}

3

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// returns height in edges; updates best with the path bending here
int height(Node *node, int &best) {
    if (node == nullptr) return -1;
    int lh = height(node->left, best);
    int rh = height(node->right, best);
    best = max(best, lh + rh + 2);   // edges through this node
    return max(lh, rh) + 1;          // height for the parent
}

int diameter(Node *root) {
    int best = 0;
    height(root, best);
    return best;
}

int main() {
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << diameter(root) << endl;
    return 0;
}

3

public class Diameter {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    // returns height in edges; updates best[0]
    static int height(Node node, int[] best) {
        if (node == null) return -1;
        int lh = height(node.left, best);
        int rh = height(node.right, best);
        best[0] = Math.max(best[0], lh + rh + 2);  // path through here
        return Math.max(lh, rh) + 1;               // height for parent
    }

    static int diameter(Node root) {
        int[] best = { 0 };
        height(root, best);
        return best[0];
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        System.out.println(diameter(root));
    }
}

3

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def diameter(root):
    best = [0]  # shared running answer

    def height(node):
        if node is None:
            return -1                  # empty: height -1 so a leaf is 0
        lh = height(node.left)         # left height
        rh = height(node.right)        # right height
        best[0] = max(best[0], lh + rh + 2)  # edges bending here
        return max(lh, rh) + 1         # height for the parent

    height(root)
    return best[0]


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(diameter(root))

3

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function diameter(root) {
  let best = 0; // shared running answer

  function height(node) {
    if (node === null) return -1;          // empty: -1 so a leaf is 0
    const lh = height(node.left);          // left height
    const rh = height(node.right);         // right height
    best = Math.max(best, lh + rh + 2);    // edges bending here
    return Math.max(lh, rh) + 1;           // height for the parent
  }

  height(root);
  return best;
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

console.log(diameter(root));

3

Let us walk through the Python version line by line so the logic is clear.

We start with best = [0]. We use a list because the inner function needs to change a value that lives outside it. A plain number would not carry the change back out. The list is a small box we can reach into.

The inner height function begins with if node is None: return -1. We return -1 for empty, not 0. Why? Because then a single leaf node, with two empty children, computes its own height as max(-1, -1) + 1, which is 0. That keeps the edge counting honest.

Next, lh = height(node.left) and rh = height(node.right) get the heights of the two sides. These calls do the deep work and also update best along the way.

Then best[0] = max(best[0], lh + rh + 2). This is the path that bends at the current node. Left height plus right height gives the inner edges. The plus 2 adds the two edges joining this node to its children. We keep the largest such value we ever see.

Finally return max(lh, rh) + 1. To the parent, this node’s height is the taller side plus one edge up. That is the value the parent needs, not the diameter.

⏱️ Time and Space Complexity

The brute force recomputes height at every node, so it slows to O(n²). The single-pass version visits each node once and does fixed work there, so it is O(n). The space is the recursion depth, which is O(h) where h is the height of the tree.

🧩 Key Takeaways

• ✅ The diameter is the longest path in edges, and it need not pass through the root.
• ✅ At each node, the bending path is left height plus right height.
• ✅ Compute height and track the diameter in the same single walk.
• ✅ Return height to the parent, but keep the diameter in a shared variable.
• ✅ The single-pass version is O(n), much faster than recomputing heights.

🚀 What’s Next?

• Balanced Binary Tree
• Subtree of Another Tree