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.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

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.

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.

Solution Implementation

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.

Learn more about how to find time and space complexity quickly using problem constraints.