Diameter of Binary Tree

Easy
1873.

Diameter of Binary Tree

Diameter of Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.

Given the root of a binary tree, return the length of its diameter: the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

Example 1

Input
root = [1,2,3,4,5]
Output
3
Explanation
The paths 4 → 2 → 1 → 3 and 5 → 2 → 1 → 3 each have three edges.

Example 2

Input
root = [1,2]
Output
1

Example 3

Input
root = [1,2,null,3,4,5,null,null,6]
Output
4
Explanation
The longest path, 5 → 3 → 2 → 4 → 6, never reaches the root.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • -100 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Diameter of Binary Tree — Solution in Python, Java & C++

Diameter of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Diameter of Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

Given the root of a binary tree, return the length of its diameter: the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

Example 1

Input: root = [1,2,3,4,5]
Output: 3
Explanation: The paths 4 → 2 → 1 → 3 and 5 → 2 → 1 → 3 each have three edges.

Example 2

Input: root = [1,2]
Output: 1

Example 3

Input: root = [1,2,null,3,4,5,null,null,6]
Output: 4
Explanation: The longest path, 5 → 3 → 2 → 4 → 6, never reaches the root.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • -100 <= Node.val <= 100

Hints for Diameter of Binary Tree

  1. Hint 1

    Every path has one highest node; at that node the path goes down into the left subtree, the right subtree, or both.

  2. Hint 2

    The longest path whose highest node is x has height(x.left) + height(x.right) edges, with height counted in nodes.

  3. Hint 3

    Compute heights bottom-up in one walk and update a running maximum of that sum at every node.

How to solve Diameter of Binary Tree

For each node, the longest path that turns at it is the height of its left subtree plus the height of its right subtree. One post-order walk computes every height once and keeps the best such sum.

Approach

  1. Define height(null) = 0.
  2. At each node, compute l = height(left) and r = height(right).
  3. Update best = max(best, l + r).
  4. Return 1 + max(l, r) as this node's height.
  5. After height(root), return best.

Why it works

Any path has a unique topmost node, and from there it descends at most once into each subtree; the longest such descent into a subtree has exactly that subtree's height in edges, counting the edge from the top node. So the best path topped at x has l + r edges, and taking the maximum over all x covers every path.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth

Pitfalls

  • The diameter counts edges, not nodes — a single node has diameter 0.
  • Returning only height(root.left) + height(root.right) misses paths that do not pass through the root (third example).
  • Computing heights separately at every node is O(n^2) on a chain.

Reference solution

Python

from typing import Optional

def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
    best = 0

    def height(node):
        nonlocal best
        if node is None:
            return 0
        l = height(node.left)
        r = height(node.right)
        best = max(best, l + r)
        return 1 + max(l, r)

    height(root)
    return best

Java

public static int diameterOfBinaryTree(TreeNode root) {
    int[] best = new int[1];
    diameterHeight(root, best);
    return best[0];
}

static int diameterHeight(TreeNode node, int[] best) {
    if (node == null) return 0;
    int l = diameterHeight(node.left, best);
    int r = diameterHeight(node.right, best);
    best[0] = Math.max(best[0], l + r);
    return 1 + Math.max(l, r);
}

C++

int diameterHeight(TreeNode* node, int& best) {
    if (!node) return 0;
    int l = diameterHeight(node->left, best);
    int r = diameterHeight(node->right, best);
    best = max(best, l + r);
    return 1 + max(l, r);
}

int diameterOfBinaryTree(TreeNode* root) {
    int best = 0;
    diameterHeight(root, best);
    return best;
}

JavaScript

var diameterOfBinaryTree = function(root) {
    var best = { value: 0 };
    diameterHeight(root, best);
    return best.value;
};

var diameterHeight = function(node, best) {
    if (node === null) return 0;
    var l = diameterHeight(node.left, best);
    var r = diameterHeight(node.right, best);
    if (l + r > best.value) best.value = l + r;
    return 1 + Math.max(l, r);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals