Find Diameter of a Binary Tree

Algorithm Steps

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.

Find Diameter of a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

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))