Diameter of a Binary Tree

JavaView on GFG

Time: O(n)

Space: O(h)

Problem Overview

Diameter passes through some node (LCA).

See our study guide for structured GFG and LeetCode practice.

Intuition

Diameter passes through some node (LCA). For each node, diameter through it = leftHeight + rightHeight. Track global maximum.

Algorithm

1DFS returning height of subtree.
2At each node: diameter candidate = leftHeight + rightHeight.
3Update global max. Return 1 + max(leftHeight, rightHeight) as height.

Example Walkthrough

Input: root=[1,2,3,4,5]

1. Node 4: h=1. Node 5: h=1. Node 2: dia=2, h=2. Node 3: h=1. Node 1: dia=1+2=3, h=3.

Output: 3

Common Pitfalls

• Diameter doesn't have to pass through root. Update global max at every node.

Diameter of a Binary Tree.java

Java

// Approach: DFS. For each node, diameter through it = height(left) + height(right). Track global max.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    int ans = 0;

    int diameter(Node root) {
        depth(root);
        return ans;
    }

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

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

        ans = Math.max(ans, left + right);

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

Was this solution helpful?