Depth-First Search
Diameter of a Binary Tree
easy
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given the root of a binary tree, write a recursive function to find the diameter of the tree. The diameter of a binary tree is the length of the longest path (# of edges) between any two nodes in a tree. This path may or may not pass through the root.
Example 1:
Input:
[3, 9, 2, 1, 4, null, null, null, 5]
Output: 4 (The longest path is 5 -> 1 -> 9 -> 3 -> 2) for a total of 4 edges
Example 2:
Input:
[3, 9, null, 1, 4, null, null, 2, null, 3]
Output: 4 (The longest path is 2 -> 1 -> 9 -> 4 -> 3) for a total of 4 edges
Explanation
The diameter of a binary tree is equal to longest path between any two nodes in the tree. So we want to use depth-first search to visit each node, and at each node we'll calculate the length of the longest path that passes through that node. At the end, we'll return the maximum of those lengths.
Now, let's breakdown how to calculate the longest path that passes through a node in the tree. As shown in the diagram below, the longest path that passes through a node is equal to the maximum depth of the nodes' left subtree + the maximum depth of the nodes' right subtree, where the depth of a subtree is the number of nodes on the longest path from the root of that subtree to a leaf node.
So at each node, we want to find the max depth of our left and right subtrees, and use that to calculate the length of the longest path that passes through that node. With that in mind, we can solve this problem using the framework described in the Overview section:
Return Values
If I'm at a node in the tree, what values do I need from my left and right children to calculate the diameter of the subtree rooted at the current node?
As we broke down above, to calculate the diameter, we need:
- The max depth of the left subtree.
- The max depth of the right subtree.
This tells us that each recursive call should return the max depth of the subtree rooted at the current node. So in the body of the recursive function, I'll make recursive calls to the current node's left and right children, and then return the max depth of the current subtree as 1 + max(left, right) to the parent.
Before returning, I should add those values together to get the diameter of the tree rooted at the current node. I can then compare that value to a global variable max_, and update max_ if necessary.
(See the Global Variables section below for more details on why this is necessary).
Solution
# get the max depth of the left and right subtreesleft = dfs(node.left)right = dfs(node.right)# update the maximum diameter of the treemax_ = max(max_, left + right)# return the max depth of the current subtreereturn 1 + max(left, right)
Base Case
The max depth of an empty tree is 0.
Global Variables
Each recursive call returns the max depth of the subtree rooted at the current node, but the question is asking for the diameter of the tree. Since these two values are different, we can use a global variable max_ to store the maximum diameter of the tree, and update it as necessary in each recursive call.
Using a global variable allows us to avoid using multiple return values in our recursive function, or having to pass the maximum diameter value as a parameter from the parent to the child.
Helper Function
We don't need to pass values from the parent to the child to solve this problem. However, since we are using a global variable to store the maximum diameter of the tree, we should define max_ inside the body of our main function, and then introduce a helper function to perform the recursive calls. This keeps the max_ variable protected, as no code outside of the main function can access it.
Inside the main function, we can initiate the call to the helper function, passing in the root of the tree as an argument. We return the value of max_ after the recursive helper function has finished executing.
Solution
Solution
class Solution:def diameterOfBinaryTree(self, root):max_ = 0def dfs(node):nonlocal max_# base caseif not node:return 0# get the max depth of the left and right subtreesleft = dfs(node.left)right = dfs(node.right)# update the maximum diameter of the treemax_ = max(max_, left + right)# return the max depth of the current subtreereturn 1 + max(left, right)dfs(root)return max_
Animated Solution
Visualization
Try these examples:
def diameterOfBinaryTree(root):max_ = 0def dfs(node):nonlocal max_if not node:return 0left = dfs(node.left)right = dfs(node.right)max_ = max(max_, left + right)return max(left, right) + 1dfs(root)return max_
diameter of binary tree
0 / 34
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N) where N is the number of nodes in the binary tree. We visit each node exactly once, so the time complexity is O(N).
Space Complexity: O(N) where N is the number of nodes in the binary tree. A total of N recursive calls are made, one for each node in the tree. Each recursive call requires a constant amount of space for the call frame.
Mark as read
Your account is free and you can post anonymously if you choose.