543. Diameter of Binary Tree


Problem Description

The task is to find the diameter of a binary tree. The diameter is the longest path between any two nodes in the tree, which does not necessarily have to involve the root node. Here, the length of the path is given by the number of edges between the nodes. Therefore, if a path goes through the sequence of nodes A -> B -> C, the length of this path is 2 since there are two edges involved (A to B and B to C).

Intuition

To solve this problem, we use a depth-first search (DFS) approach. The intuition behind using DFS is to explore as far as possible down each branch before backtracking, which helps in calculating the depth (or height) of each subtree rooted at node.

For every node, we compute the depth of its left and right subtrees, which are the lengths of the longest paths from this node to a leaf node down the left and right subtrees, respectively. The diameter through this node is the sum of these depths, as it represents a path from the deepest leaf in the left subtree, up to the current node, and then down to the deepest leaf in the right subtree.

The key is to recognize that the diameter at each node is the sum of the left and right subtree depths, and we are aiming to find the maximum diameter over all nodes in the tree. Hence, during the DFS, we keep updating a global or external variable with the maximum diameter found so far.

One crucial aspect of the solution is that for every DFS call, we return the depth of the current subtree to the previous caller (parent node) in order to compute the diameter at the parent level. The current node depth is calculated as 1 + max(left, right), accounting for the current node itself plus the deeper path among its left or right subtree.

This approach allows us to travel only once through the tree nodes, maintaining a time complexity of O(N), where N is the number of nodes in the tree.

Solution Approach

To implement the diameter calculation for a binary tree, we use DFS to traverse the tree. Here's a step-by-step breakdown of the algorithm used in the provided code:

  1. Define the dfs Function: This recursive function takes a node of the tree as an argument. Its purpose is to compute the depth of the subtree rooted at that node and update the ans variable with the diameter passing through that node.

  2. Base Case: If the current node is None, which means we've reached beyond a leaf node, we return a depth of 0.

  3. Recursive Search: We calculate the depth of the left subtree (left) and the depth of the right subtree (right) by making recursive calls to dfs(root.left) and dfs(root.right).

  4. Update Diameter: We update the ans variable (which is declared with the nonlocal keyword to refer to the ans variable in the outer scope) with the maximum of its current value and the sum of left and right. This represents the largest diameter found at the current node because it is the sum of the path through the left child plus the path through the right child.

  5. Returning Depth: Each call to dfs returns the depth of the subtree it searched. The depth is the maximum between the depths of its left and right subtrees, increased by 1 to account for the current node.

  6. Start DFS: We call dfs starting at the root node to initiate the depth-first search of the tree.

  7. Return the Result: After traversing the whole tree, ans holds the length of the longest path, which is the diameter of the binary tree.

The overall complexity of the solution is O(N), where N is the number of nodes in the binary tree since each node is visited exactly once.

This solution uses a DFS pattern to explore the depth of each node’s subtrees and a global or "helper" scope variable to track the cumulative maximum diameter found during the entire traversal. The use of recursion and tracking a global maximum is a common strategy for tree-based problems where computations in child nodes need to influence a result variable at a higher scope.

The use of a nonlocal keyword in Python is essential here as it allows the nested dfs helper function to modify the ans variable defined in the outer diameterOfBinaryTree function's scope.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the depth-first search (DFS) algorithm to find the diameter of a binary tree.

Consider a binary tree:

1     1
2    / \
3   2   3
4  / \
5 4   5

In this example, the longest path (diameter) is between node 4 and node 3, which goes through node 2 and node 1. Here's how we can apply the solution approach to this tree:

  1. We start DFS with the root node. Let's call dfs(1):

    • It's not None, so we continue with the recursion.
  2. We encounter node 1 and make recursive calls to its left and right children:

    • dfs(2) is called for the left subtree.
    • dfs(3) is called for the right subtree.
  3. Inside dfs(2):

    • We call dfs(4) for the left child and return 1 (since 4 is a leaf node).
    • We call dfs(5) for the right child and return 1 (since 5 is a leaf node).
    • We update ans to be max(ans, left + right) which at this point is max(0, 1 + 1) = 2.
    • We return 1 + max(left, right) to indicate the depth from node 2 to the deepest leaf which equals 1 + 1 = 2.
  4. Inside dfs(3):

    • Since node 3 is a leaf node, we return 1.
  5. Back to the dfs(1), with the returned values:

    • We received 2 from the left subtree (dfs(2)).
    • We received 1 from the right subtree (dfs(3)).
    • We update ans with the sum of the left and right which is max(2, 2 + 1) = 3. This is the diameter passing through the root.
  6. DFS is called throughout the entire tree, and the maximum value of ans is updated accordingly.

  7. Since we've traversed the whole tree, the final ans is 3, which is the length of the longest path (diameter) in our binary tree, passing from node 4 to 3 via nodes 2 and 1.

The key steps in the example above show the recursive nature of the solution, updating a global maximum diameter as the recursion unfolds, and the use of depth calculations to facilitate this process. The time complexity is O(N) as we visit each node exactly once in the process.

Python Solution

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def diameterOfBinaryTree(self, root: TreeNode) -> int:
9        # Helper function to perform depth-first search and calculate depth.
10        def dfs(node):
11            # If the node is None, then this is a leaf so we return 0.
12            if node is None:
13                return 0
14            nonlocal max_diameter
15            # Recursively find the depths of the left and right subtrees.
16            left_depth = dfs(node.left)
17            right_depth = dfs(node.right)
18            # Update the maximum diameter found so far.
19            # Diameter at this node will be the sum of depths of left & right subtrees.
20            max_diameter = max(max_diameter, left_depth + right_depth)
21            # Return the depth of this node which is max of left or right subtree depths plus 1.
22            return 1 + max(left_depth, right_depth)
23
24        # Initialize the maximum diameter as 0.
25        max_diameter = 0
26        # Start the DFS traversal from the root.
27        dfs(root)
28        # Finally, return the maximum diameter found.
29        return max_diameter
30

Java Solution

1/**
2 * Definition for a binary tree node.
3 * This class represents a node in a binary tree, with a value and pointers to its left and right child nodes.
4 */
5class TreeNode {
6    int val;
7    TreeNode left;
8    TreeNode right;
9  
10    TreeNode() {}
11
12    TreeNode(int val) { this.val = val; }
13  
14    TreeNode(int val, TreeNode left, TreeNode right) {
15        this.val = val;
16        this.left = left;
17        this.right = right;
18    }
19}
20
21/**
22 * This class contains methods to solve for the diameter of a binary tree.
23 */
24class Solution {
25    private int maxDiameter; // Holds the maximum diameter found
26
27    /**
28     * Finds the diameter of a binary tree, which is the length of the longest path between any two nodes in a tree.
29     * This path may or may not pass through the root.
30     * 
31     * @param root the root node of the binary tree
32     * @return the diameter of the binary tree
33     */
34    public int diameterOfBinaryTree(TreeNode root) {
35        maxDiameter = 0;
36        depthFirstSearch(root);
37        return maxDiameter;
38    }
39
40    /**
41     * A recursive method that calculates the depth of the tree and updates the maximum diameter.
42     * The path length between the nodes is calculated as the sum of the heights of left and right subtrees.
43     *
44     * @param node the current node
45     * @return the maximum height from the current node
46     */
47    private int depthFirstSearch(TreeNode node) {
48        if (node == null) {
49            // Base case: if the current node is null, return a height of 0
50            return 0;
51        }
52        // Recursively find the height of the left and right subtrees
53        int leftHeight = depthFirstSearch(node.left);
54        int rightHeight = depthFirstSearch(node.right);
55      
56        // Update the maximum diameter if the sum of heights of the current node's subtrees is greater
57        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
58      
59        // Return the max height seen up to the current node, including the current node's height (which is 1)
60        return 1 + Math.max(leftHeight, rightHeight);
61    }
62}
63

C++ Solution

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    // Class member to keep track of the maximum diameter found.
15    int maxDiameter;
16
17    // This function initializes the maxDiameter to zero and starts the DFS traversal.
18    int diameterOfBinaryTree(TreeNode* root) {
19        maxDiameter = 0;
20        depthFirstSearch(root);
21        return maxDiameter;
22    }
23
24    // Helper function for DFS traversal of the tree.
25    // Calculates the depth of the tree and updates the maximum diameter.
26    int depthFirstSearch(TreeNode* node) {
27        if (node == nullptr) return 0;  // Base case: return zero for null nodes.
28
29        // Recursive DFS on the left child.
30        int leftDepth = depthFirstSearch(node->left);
31        // Recursive DFS on the right child.
32        int rightDepth = depthFirstSearch(node->right);
33
34        // Update the maximum diameter if the current node's diameter is greater.
35        maxDiameter = max(maxDiameter, leftDepth + rightDepth);
36
37        // Return the maximum depth from this node down to the leaf.
38        return 1 + max(leftDepth, rightDepth);
39    }
40};
41

Typescript Solution

1// Definition for a binary tree node.
2class TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6
7  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8    this.val = val === undefined ? 0 : val;
9    this.left = left === undefined ? null : left;
10    this.right = right === undefined ? null : right;
11  }
12}
13
14// Variable to hold the final result - the diameter of the binary tree.
15let diameter: number = 0;
16
17/**
18 * A depth-first search function to traverse the tree and calculate
19 * the diameter of the binary tree.
20 * 
21 * @param {TreeNode | null} node - The current node being visited.
22 * @returns {number} - The height of the current node.
23 */
24function depthFirstSearch(node: TreeNode | null): number {
25  // Base case: if the node is null, return a height of 0.
26  if (node === null) {
27    return 0;
28  }
29
30  // Calculate the height of the left and right subtrees.
31  const leftHeight = depthFirstSearch(node.left);
32  const rightHeight = depthFirstSearch(node.right);
33
34  // Update the diameter if the sum of left and right heights is larger than the current diameter.
35  diameter = Math.max(diameter, leftHeight + rightHeight);
36
37  // Return the height of the current node, which is max of left or right subtree height plus 1.
38  return Math.max(leftHeight, rightHeight) + 1;
39}
40
41/**
42 * Calculates the diameter of a binary tree - the length of the longest
43 * path between any two nodes in a tree. This path may or may not pass through the root.
44 * 
45 * @param {TreeNode | null} root - The root node of the binary tree.
46 * @returns {number} - The diameter of the binary tree.
47 */
48function diameterOfBinaryTree(root: TreeNode | null): number {
49  // Initialize diameter to 0 before starting DFS.
50  diameter = 0;
51
52  // Start DFS traversal from the root to calculate the diameter.
53  depthFirstSearch(root);
54
55  return diameter;
56}
57

Time and Space Complexity

Time Complexity

The time complexity of the diameterOfBinaryTree method is O(n), where n is the number of nodes in the binary tree. This is because the auxiliary function dfs is called exactly once for each node in the tree. In the dfs function, the work done at each node is constant time, primarily consisting of calculating the maximum of the left and right heights and updating the ans variable if necessary.

Space Complexity

The space complexity of the diameterOfBinaryTree method is O(h), where h is the height of the binary tree. This accounts for the maximum number of recursive calls that stack up on the call stack at any point during the execution of the dfs function. In the worst case, where the tree is skewed (forms a straight line), the height of the tree can be n, leading to a space complexity of O(n). However, in a balanced tree, the height h would be O(log n), leading to a more efficient space utilization.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫