Find Diameter of a Binary Tree - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

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.

Examples❯

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)

Visualization Player

Solution❯

Case 1: Normal Binary Tree

In a regular binary tree with multiple levels, the diameter may pass through the root or it may lie in one of the subtrees. For example, in the tree [1, 2, 3, 4, 5], the longest path (diameter) is from node 4 to node 5 through their common ancestor node 2, and potentially up through the root node 1. The key is to check the height of the left and right subtrees at every node and consider the sum of both as a candidate for the diameter.

Case 2: Single Node Tree

When the binary tree consists of only one node, like [1], there are no edges connecting different nodes. Therefore, the longest path is 0, and the diameter is 0.

Case 3: Empty Tree

If the input tree is empty (i.e., the root is null), there are no nodes or edges. Hence, the diameter is also 0. This is an important edge case to handle programmatically to avoid null reference errors.

Case 4: Skewed Tree (like a Linked List)

In skewed trees where each node only has one child (all left or all right), the diameter is the total number of edges between the topmost and bottommost nodes. For example, in the tree [1, 2, null, 3, null, 4], the diameter is 3, as the longest path includes all the edges in the skewed direction.

Case 5: Uneven Subtrees

In trees where left and right subtrees have different depths, like [1, 2, 3, 4, null, null, 5], the diameter may span from the deepest node on the left to the deepest node on the right. This may not go through the root but through an intermediate node. We need to consider all such paths to find the maximum one.

Algorithm Steps❯

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

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #       /   \
    #      2     3
    #     / \   
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(diameterOfBinaryTree(root))