Diameter of Binary Tree easy

Problem Statement

Given a binary tree, you need to find the maximum 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.

Example 1

Input:

      1
     / \
    2   3
   / \
  4   5

Output: 3 Explanation: The diameter of the tree is 3, which is the length of the path between nodes 4 and 5.

Example 2

Input:

      1
     /
    2
   /
  3

Output: 2 Explanation: The diameter of the tree is 2, which is the length of the path between nodes 3 and 2.

Steps

  1. Depth-First Search (DFS): We'll use a recursive DFS approach to traverse the tree.
  2. Height Calculation: For each node, we calculate its height (the maximum depth from that node). The height of a leaf node is 0.
  3. Diameter Calculation: The diameter at a given node is the sum of the heights of its left and right subtrees. We'll keep track of the maximum diameter encountered so far.
  4. Return Value: The function returns the height of the subtree rooted at the current node, and the maximum diameter is maintained as a global variable.

Explanation

The key idea is that the diameter either passes through the root or it doesn't. If it passes through the root, it's the sum of the heights of the left and right subtrees. If it doesn't, it's the maximum diameter found in the left and right subtrees. Therefore, we recursively compute the height of each subtree and update the maximum diameter accordingly.

Code

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.max_diameter = 0  # Initialize maximum diameter

        def dfs(node):
            if not node:
                return 0  # Height of an empty subtree is 0

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

            # Update max_diameter
            self.max_diameter = max(self.max_diameter, left_height + right_height)

            # Return height of current subtree
            return max(left_height, right_height) + 1

        dfs(root)
        return self.max_diameter

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once during the DFS traversal.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack used in the DFS. In the worst case (a skewed tree), H can be equal to N. In a balanced tree, H is log(N).