Diameter of a Binary Tree - codepath/compsci_guides GitHub Wiki

Unit 12 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Trees, Depth-First Search (DFS), Recursion

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • What is the diameter of a tree?

    • The longest path between any two nodes in the tree. This path can traverse any part of the tree and is measured by the number of edges.

  • Can the diameter pass through the root node?

    • Yes, but it doesn't have to.
HAPPY CASE
Input: 
    1                
   /  \         
  2    3    
 / \        
4   5      

Output: 3
Explanation: Longest path is [4, 2, 1, 3] or [5, 2, 1, 3].

Input: 
   1
  /
 2

Output: 1
Explanation: The longest path is [2, 1].

EDGE CASE
Input: root = None
Output: 0
Explanation: An empty tree has a diameter of 0.

Input: root = TreeNode(1)
Output: 0
Explanation: A single node tree has no edges, so the diameter is 0.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Tree Traversal and Diameter problems, we want to consider the following approaches:

  • Depth-First Search (DFS): Recursively explore all paths to find the height of each subtree and the diameter.
  • Recursion with Backtracking: Use recursive calls to return the height of each subtree while calculating the diameter.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a recursive DFS traversal to calculate the height of each node's left and right subtrees. As we calculate the height, we also update the diameter if the sum of the left and right heights at any node is greater than the current diameter.

1) Initialize a `diameter` variable to 0 to track the maximum path found.
2) Define a helper function `dfs(node)` that:
   a) Returns 0 if the current node is None (base case).
   b) Recursively calculates the height of the left and right subtrees.
   c) Updates the diameter using the sum of left and right heights.
   d) Returns the height of the current node as 1 + max(left, right).
3) Call `dfs` on the root to start the traversal.
4) Return the final value of the `diameter`.

⚠️ Common Mistakes

  • Forgetting to use nonlocal or global variables for tracking the diameter.
  • Not handling the case where the tree is empty (root is None).

4: I-mplement

Implement the code to solve the algorithm.

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

def tree_diameter(root):
    diameter = 0
    
    def dfs(node):
        nonlocal diameter
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        diameter = max(diameter, left + right)
        return max(left, right) + 1

    dfs(root)
    return diameter

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: Tree with structure:

         1                
    /  \         
   2    3    
  / \        
 4   5
    • At node 2: left height = 1, right height = 1, diameter = 2
    • At node 1: left height = 2, right height = 1, diameter = 3
    • Output: 3

  • Input: Tree with structure:

      1
 /
2
    • At node 1: left height = 1, right height = 0, diameter = 1
    • Output: 1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes in the tree.

  • Time Complexity: O(N) because we visit every node exactly once.
  • Space Complexity: O(N) in the worst case due to the recursive stack when the tree is skewed.