Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Easy

Diameter of Binary Tree

Diameter of a binary tree explained: why the longest path bends at some node, the O(n) height-plus-global-max trick, tested Python code and a live tree visual.

Also searched as: longest path between two nodes in a binary tree · tree diameter in O(n)

🌳

Try it live Free

Binary Search Tree & Traversals

Build a tree in the BST lab with one deep branch on the left and try to spot the node where the longest path bends; it is often not the root.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

The diameter of a binary tree is the number of edges on the longest path between any two nodes. The path does not have to pass through the root. Given the root, return the diameter.

Inputroot = [1, 2, 3, 4, 5]
Output3

The path 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3) has 3 edges.

The key insight

Every path has one highest node where it bends. If the path bends at node X, its length is height(left of X) + height(right of X). So compute heights bottom-up as usual, and at every node update a global best with left height plus right height. The function returns height; the answer lives in the side variable.

Brute force first: Computing the left and right heights from scratch at every node is O(n²) for a skewed tree.

Step-by-step approach

  1. Keep a variable best = 0 outside the recursion.
  2. Write height(node) returning 0 for None.
  3. At each node, get l = height(left) and r = height(right).
  4. Update best = max(best, l + r): the longest path that bends here.
  5. Return 1 + max(l, r) to the parent, and finally return best.

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def diameter_of_binary_tree(root):
    best = 0
    def height(node):                  # height in nodes
        nonlocal best
        if node is None:
            return 0
        l, r = height(node.left), height(node.right)
        best = max(best, l + r)        # path bending at this node, in edges
        return 1 + max(l, r)
    height(root)
    return best

Complexity

TimeO(n)
SpaceO(h)

One post-order pass visits each node once. The recursion stack is the tree height h.

Common mistakes

Frequently asked questions

What is the time and space complexity of the diameter solution?

O(n) time with the single-pass height trick and O(h) extra space for the recursion stack, where h is the height of the tree.

Does the diameter always pass through the root?

No. If one subtree is much deeper and bushier, the longest path can bend at a node inside it, which is why you track a global maximum at every node.

How does this relate to Binary Tree Maximum Path Sum?

It is the same template with weights: each node returns the best downward path sum and updates a global answer with node value plus the best left and right contributions, ignoring negative ones.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.