Diameter of Binary Tree easy

Problem Statement

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.

Example 1

Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2

Input: root = [1,2] Output: 1

Steps

  1. Depth-First Search (DFS): We'll use a recursive DFS approach to traverse the tree.
  2. Maximum Depth: For each node, we need to find the maximum depth of its left and right subtrees. The maximum depth of a node is the length of the longest path from that node to a leaf node.
  3. Diameter Calculation: The diameter at a given node is the sum of the maximum depths of its left and right subtrees.
  4. Global Maximum: We'll keep track of the global maximum diameter encountered during the traversal.

Explanation

The key insight is that the diameter may not necessarily pass through the root. Therefore, we need to explore all possible paths. Our DFS function calculates the maximum depth of a subtree rooted at a given node. The diameter at a node is the sum of the maximum depths of its left and right subtrees. We track the maximum diameter found across the entire tree.

Code

class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root); // Call to initiate the traversal
        return maxDiameter;
    }

    private int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);

        // Update the maximum diameter
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        // Return the maximum depth of the current subtree
        return 1 + Math.max(leftDepth, rightDepth); 
    }
}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node 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 traversal. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is logâ‚‚N.