Depth-First Search
Longest Univalue Path
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given the root of the binary tree, find the longest path where all nodes along the path have the same value. This path doesn't have to include the root node, and it can bend at a node to connect that node's left and right subtrees (as in Example 2 below). Return the number of edges on that path, not the number of nodes.
Example 1:
Input:
[1,4,5,4,4,5]
Output: 2
Explanation: The longest path of the same value is the path [4,4,4], which has a total of 2 edges.
Example 2:
Input:
[1,1,1,1,1,1,1]
Output: 4
Explanation: The longest path of the same value is the path [1,1,1,1,1], which has a length of 4.
Explanation
We can solve this question using a Post-Order Traversal of the tree, using a similar approach to the Diameter of a Binary Tree problem.
We'll visit each node in the binary tree, and at each node, we'll calculate the length of the longest univalue path that is rooted at that node. We'll then return the longest of those paths at the end. In order to do this in one pass, we'll use a bottom-up approach, or Post-Order Traversal.
Calculating the Longest Univalue Path at a Node
The idea is to have each recursive call return the length of the longest univalue path that is rooted at the current node to its parent. This way, the parent can use the return values from its children to calculate the longest univalue path that passes through the current node.
Let's look at an example of how this works:
If the current node is a leaf node, then the longest univalue path rooted at those nodes is 0.
Those values are received by the parent node, which uses them to calculate the longest univalue path that passes through its node.
The parent first checks if the value of the current node matches the value of its children. If it does, the parent can calculate the longest univalue path that passes through its node by adding 1 to the longest univalue path of its children.
The parent node now returns the length of the longest univalue path rooted through its node to its parent, and the process will continue until we have visited all nodes in the tree.
Let's visualize another example.
Starting from the leaf nodes:
Node 4 receives those two values, and can extend the longest univalue path that passes through it by 2, since it has the same value as its left and right children.
Now, Node 4 returns the longest univalue path rooted at its node to its parent, which is only 1, as this is the only path that the parent can possibly extend in order to calculate its own longest univalue path.
Using the framework describe in the Overivew section:
Return Values
Each node returns the length of the longest univalue path rooted at its node to its parent.
Base Case
An empty node returns 0, as it does not have any univalue path rooted at its node.
Global Variables
Note that the problem is asking for the length of the longest univalue that goes through a node, not necessarily rooted at a node, which is a different value than what each recursive call returns from the return values.
This means we have to keep track of the longest univalue path that goes through a node, which is stored in a global variable max_length.
Extra Work
At each node, after receiving the return values from its children, we have to check if the node can extend the longest univalue path that goes through it by checking if the value of the node matches the value of its children. We can extend the longest univalue path by 1 for each child that has the same value as the node.
Then, we can update the global variable max_length with the length of the longest univalue path that goes through the current node.
Solution
Solution
Python
class Solution:def longestUnivaluePath(self, root):max_length = 0def dfs(node):nonlocal max_lengthif not node:return 0left_length = dfs(node.left)right_length = dfs(node.right)left_arrow = right_arrow = 0# check if children have the same value as the current node,# which means we can extend the univalue path by including the# current nodeif node.left and node.left.val == node.val:left_arrow = left_length + 1if node.right and node.right.val == node.val:right_arrow = right_length + 1# left_arrow + right_arrow is the length of the longest# univalue path that goes through the current nodemax_length = max(max_length, left_arrow + right_arrow)return max(left_arrow, right_arrow)dfs(root)return max_length
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 tree. We visit each node exactly once, and at each node, we perform constant time work.
Space Complexity: O(N) where N is the number of nodes. A total of N call frames have to be allocated, one for each node in the tree in the worst case (in the case of a skewed tree, where each node only has one child).
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.