Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0543 - Diameter of Binary Tree
    0543 - Diameter of Binary Tree
    0543 - Diameter of Binary Tree
    0543 - Diameter of Binary Tree

    0543 - Diameter of Binary Tree

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/diameter-of-binary-tree/

    Solution 1 - DFS (Depth-First Search)

    At each node, compute the depth of its left and right subtrees. The diameter through that node is the sum of both depths. Track the maximum diameter seen across all nodes using a nonlocal variable. Return the max depth from each subtree to the parent for further computation.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(h)SpaceComplexity: O(h)SpaceComplexity:O(h)

    Solution 2 - DFS with Tuple Return

    Instead of using an instance variable to track the diameter, each recursive call returns a tuple of (diameter, depth). The diameter at each node is the max of the left diameter, right diameter, and the sum of both depths. This avoids mutable state entirely.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(h)SpaceComplexity: O(h)SpaceComplexity:O(h)
    """ 0543.1 - Diameter of Binary Tree - Solution 1 - DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        """Diameter of Binary Tree Function"""
        self.diameter = 0

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            self.diameter = max(self.diameter, left + right)

            return 1 + max(left, right)

        dfs(root)
        return self.diameter


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: root = [1,2,3,4,5] -> Output: 3
    root1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(Solution().diameterOfBinaryTree(root1))  # 3

    # Example 2: root = [1,2] -> Output: 1
    root2 = TreeNode(1, TreeNode(2))
    print(Solution().diameterOfBinaryTree(root2))  # 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0543.2 - Diameter of Binary Tree - Solution 2 - DFS with Tuple Return """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        """Diameter of Binary Tree Function"""

        def dfs(node: Optional[TreeNode]) -> tuple:
            if not node:
                return (0, 0)

            left_diameter, left_depth = dfs(node.left)
            right_diameter, right_depth = dfs(node.right)

            current_diameter = left_depth + right_depth
            max_diameter = max(left_diameter, right_diameter, current_diameter)
            max_depth = 1 + max(left_depth, right_depth)

            return (max_diameter, max_depth)

        diameter, _ = dfs(root)
        return diameter


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: root = [1,2,3,4,5] -> Output: 3
    root1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(Solution().diameterOfBinaryTree(root1))  # 3

    # Example 2: root = [1,2] -> Output: 1
    root2 = TreeNode(1, TreeNode(2))
    print(Solution().diameterOfBinaryTree(root2))  # 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()