We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Diameter of Binary Tree

Difficulty: Easy

Problem Description

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.

Key Insights

  • The diameter can be found by calculating the longest path between any two nodes.
  • The longest path can be found by determining the maximum depth of the left and right subtrees for each node.
  • The diameter at a node is the sum of the heights of its left and right subtrees.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the tree, as we visit each node once. Space Complexity: O(H) - where H is the height of the tree, due to the recursion stack.

Solution

To solve the problem, we will use a depth-first search (DFS) approach. We will traverse the binary tree and calculate the height of the left and right subtrees for each node. The diameter at each node is the sum of these two heights. We will keep track of the maximum diameter found during the traversal.

  1. Define a recursive function to calculate the height of the tree.
  2. At each node, calculate the height of the left and right children.
  3. Update the maximum diameter using the sum of the heights of the left and right subtrees.
  4. Return the height of the current node.

Code Solutions

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

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter = 0
        
        def height(node):
            if not node:
                return 0
            left_height = height(node.left)  # Recursively find height of left subtree
            right_height = height(node.right)  # Recursively find height of right subtree
            
            # Update the diameter
            self.diameter = max(self.diameter, left_height + right_height)
            
            # Return the height of the current node
            return 1 + max(left_height, right_height)
        
        height(root)  # Start the recursion
        return self.diameter
← Back to All Questions