Diameter of Binary Tree

Introduction

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

tree-node.py

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

Solutions

1. Using DFS

This solution uses DFS to traverse all the nodes in the binary tree until it reaches the leaf nodes. At each step, it recursively computes the depth of the left and right subtrees and updates the maximum diameter accordingly.

main.py

def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
    max_length = 0

    def dfs(node: TreeNode):
        nonlocal max_length
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        max_length = max(max_length, left + right)
        return max(left, right) + 1

    dfs(root)
    return max_length

Introduction

Solutions

1. Using DFS

References