Find Diameter of a Binary Tree

Problem and examples

Given the root of a binary tree, determine the diameter of the tree. The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length is measured by the number of edges between the nodes.

Input Tree	Level Order Output	Description
[1, 2, 3, 4, 5, null, 6]	[[1], [2, 3], [4, 5, 6]]	Standard case: Diameter passes through left and right subtrees (4→2→1→3→6), length 4
[1]	[[1]]	Edge case: Single-node tree, diameter is 0 (no edges)
[]	[]	Edge case: Empty tree, diameter is 0
[1, 2, null, 3, null, null, null, 4]	[[1], [2], [3], [4]]	Left-skewed tree: Diameter is 3 (path from 4 to 1)
[1, null, 2, null, null, null, 3]	[[1], [2], [3]]	Right-skewed tree: Diameter is 2 (path from 1 to 3)
[1, 2, 3, 4, null, null, 5]	[[1], [2, 3], [4, 5]]	Diameter is 4 (path from 4 → 2 → 1 → 3 → 5)

Explore Find Diameter of a Binary Tree

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The "length" here is measured in terms of the number of edges between the nodes on the path.

For example, in the binary tree [1, 2, 3, 4, 5], one possible longest path is from node 4 to node 5. The diameter in this case is 3 (edges between 4-2, 2-1, and 1-3).

Step-by-Step Solution with Example

step 1: Understand what needs to be calculated

We need to find the **longest path** between any two nodes in the binary tree. This path can lie completely in the left or right subtree or pass through the root.

step 2: Define a helper function to calculate height

We recursively calculate the height of each node’s left and right subtree. The height of a node is the maximum number of edges on the longest path from the node to a leaf.

step 3: At each node, compute the potential diameter

At every node, we calculate the sum of the left and right subtree heights. This value represents the diameter passing through that node.

step 4: Keep track of the global maximum diameter

As we compute diameters through all nodes, we update a global variable if the current node's diameter is greater than the previous maximum.

step 5: Return the final maximum diameter

After traversing the entire tree, the global variable holds the length of the longest path, i.e., the diameter.

step 6: Example with tree [1, 2, 3, 4, 5]

Let's consider the binary tree:

        1
       /       2   3
     /     4   5

Height of 4 = 0
Height of 5 = 0
Height of 2 = max(0, 0) + 1 = 1
Diameter at node 2 = height(4) + height(5) = 0 + 0 = 0 (wrong!)
Actually, we include the edge count between nodes: so diameter at node 2 = 1 + 1 = 2
Height of 3 = 0
Diameter at root node 1 = height(2) + height(3) = 2 + 1 = 3

So, the maximum diameter is 3 (edges in path 4-2-1-3).

Edge Cases

Single Node Tree

If the tree has only one node like [1], there are no edges. So, the diameter is 0.

Empty Tree

If the tree is empty (root is null), then the diameter is 0. This must be handled to avoid runtime errors.

Skewed Tree (like Linked List)

Example: [1, 2, null, 3, null, 4] (a left-skewed tree). The diameter is 3 (edges between 1-2, 2-3, 3-4).

Uneven Subtrees

Example: [1, 2, 3, 4, null, null, 5]. Even though one subtree is deeper, the longest path can still pass through intermediate nodes, not necessarily the root.

Balanced vs Unbalanced Trees

In a balanced tree, the diameter often passes through the root. In unbalanced trees, it might lie entirely within the deeper subtree.

Finally

The key idea is to recursively calculate subtree heights and use them to determine the longest path at each node. Even though we’re calculating heights, the goal is to keep track of the **maximum** left+right height combination seen so far.

This approach ensures that all possible paths are considered, including those not passing through the root. Handling edge cases like empty trees or skewed trees makes the solution robust and beginner-friendly.

Start at the root of the binary tree.
For each node, recursively compute the height of its left and right subtrees.
The diameter at that node is the sum of the left and right subtree heights.
Update the global maximum diameter if this sum is greater than the current maximum.
Return the height of the node as max(left, right) + 1.
After processing the entire tree, the maximum diameter recorded is the tree's diameter.

Implementation and efficiency

C implementation

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

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

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

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

int diameter = 0;

int height(TreeNode* node) {
    if (node == NULL) return 0;
    int left = height(node->left);
    int right = height(node->right);
    diameter = max(diameter, left + right);
    return max(left, right) + 1;
}

int diameterOfBinaryTree(TreeNode* root) {
    diameter = 0;
    height(root);
    return diameter;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Diameter: %d\n", diameterOfBinaryTree(root));
    return 0;
}

C++ implementation

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int diameter = 0;
    int height(TreeNode* node) {
        if (!node) return 0;
        int left = height(node->left);
        int right = height(node->right);
        diameter = max(diameter, left + right);
        return max(left, right) + 1;
    }
    
    int diameterOfBinaryTree(TreeNode* root) {
        diameter = 0;
        height(root);
        return diameter;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    Solution sol;
    cout << "Diameter: " << sol.diameterOfBinaryTree(root) << endl;
    return 0;
}

Python implementation

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

def diameterOfBinaryTree(root):
    diameter = 0
    
    def height(node):
        nonlocal diameter
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        diameter = max(diameter, left + right)
        return max(left, right) + 1

    height(root)
    return diameter

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print("Diameter:", diameterOfBinaryTree(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class DiameterTree {
    int diameter = 0;

    int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left);
        int right = height(node.right);
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        height(root);
        return diameter;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        DiameterTree dt = new DiameterTree();
        System.out.println("Diameter: " + dt.diameterOfBinaryTree(root));
    }
}

JavaScript implementation

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

function diameterOfBinaryTree(root) {
    let diameter = 0;

    function height(node) {
        if (!node) return 0;
        let left = height(node.left);
        let right = height(node.right);
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    }

    height(root);
    return diameter;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log("Diameter:", diameterOfBinaryTree(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var diameter int

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    left := height(node.Left)
    right := height(node.Right)
    if left+right > diameter {
        diameter = left + right
    }
    if left > right {
        return left + 1
    }
    return right + 1
}

func diameterOfBinaryTree(root *TreeNode) int {
    diameter = 0
    height(root)
    return diameter
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}
    fmt.Println("Diameter:", diameterOfBinaryTree(root))
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn height(node: Option<Rc<RefCell<TreeNode>>>, diameter: &mut i32) -> i32 {
        if let Some(node) = node {
            let left = height(node.borrow().left.clone(), diameter);
            let right = height(node.borrow().right.clone(), diameter);
            *diameter = (*diameter).max(left + right);
            return 1 + left.max(right);
        }
        0
    }
    let mut diameter = 0;
    height(root, &mut diameter);
    diameter
}

fn main() {
    let root = TreeNode::new(1);
    let left = TreeNode::new(2);
    let right = TreeNode::new(3);
    let left_left = TreeNode::new(4);
    let left_right = TreeNode::new(5);
    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right);
    left.borrow_mut().left = Some(left_left);
    left.borrow_mut().right = Some(left_right);
    println!("Diameter: {}", diameter_of_binary_tree(Some(root)));
}

Kotlin implementation

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    var diameter = 0

    fun diameterOfBinaryTree(root: TreeNode?): Int {
        fun height(node: TreeNode?): Int {
            if (node == null) return 0
            val left = height(node.left)
            val right = height(node.right)
            diameter = maxOf(diameter, left + right)
            return maxOf(left, right) + 1
        }
        diameter = 0
        height(root)
        return diameter
    }
}

fun main() {
    val root = TreeNode(1).apply {
        left = TreeNode(2).apply {
            left = TreeNode(4)
            right = TreeNode(5)
        }
        right = TreeNode(3)
    }
    println("Diameter: ${Solution().diameterOfBinaryTree(root)}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class Solution {
    var diameter = 0
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        func height(_ node: TreeNode?) -> Int {
            guard let node = node else { return 0 }
            let left = height(node.left)
            let right = height(node.right)
            diameter = max(diameter, left + right)
            return max(left, right) + 1
        }
        diameter = 0
        height(root)
        return diameter
    }
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
print("Diameter: \(Solution().diameterOfBinaryTree(root))")

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function diameterOfBinaryTree(root: TreeNode | null): number {
    let diameter = 0;

    function height(node: TreeNode | null): number {
        if (!node) return 0;
        const left = height(node.left);
        const right = height(node.right);
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    }

    height(root);
    return diameter;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log("Diameter:", diameterOfBinaryTree(root));