687. Longest Univalue Path
Problem Description
The given problem requires us to find the length of the longest path in a binary tree, where all the nodes along the path have the same value. A path in a binary tree is a sequence of nodes where there is an edge between any two consecutive nodes in the sequence, and the length of the path is represented by the number of edges in that sequence. This specific path can start and end at any node, not necessarily including the root.
Flowchart Walkthrough
To determine the appropriate algorithm for solving LeetCode 687. Longest Univalue Path, let's utilize the algorithm flowchart provided at the Flowchart. Here's a step-by-step analysis:
Is it a graph?
- Yes: The problem involves a binary tree which is a type of graph, where nodes (tree elements) are connected by edges (links to children).
Is it a tree?
- Yes: The binary tree structure in this problem obeys the definition of a tree (a connected acyclic graph).
From here, as it is a tree:
- We directly proceed with Depth-First Search (DFS) as suggested by the path provided in the flowchart. DFS is highly suitable for tree-related problems because it can traverse all nodes of the tree efficiently and is useful particularly in problems that require exploring all connections deeply, such as finding the longest univalue path.
Conclusion: According to the flowchart, Depth-First Search (DFS) is the appropriate algorithm to solve this tree-based problem. This method will allow for a thorough exploration of paths within the tree to determine the longest univalue path.
Intuition
To solve this problem, we employ a depth-first search (DFS) strategy to traverse the tree. The key intuition here is to use recursion to explore each subtree to find the longest path with equal node values that start from the current node and extend downwards. Once a node is reached by the recursion:
- If the node is null, we cannot extend the path, so we return zero.
- We recursively obtain the lengths of the paths extending from its left and right child nodes that have the same value as the current node.
- To build the answer for the current node, we consider these cases:
- If the left child's value equals the current node's value, we increment the left path length by one to include the current node; otherwise, the longest path starting from the current node towards the left is zero, since the values don't match.
- Similarly, if the right child's value equals the current node's value, we increment the right path length by one; if not, the right path's length is zero.
- The longest path that goes through the current node (but not necessarily includes it) is the sum of the left and right path lengths we just calculated. We update our global answer,
ans
, if this sum is larger than the current answer. - Each call needs to return the maximum length from either the left or the right that includes the current node. We can't return both as we are considering paths, not splits; so we return the larger of the two.
In the provided solution, dfs
is our recursive function, and ans
is the variable that keeps track of the longest path found so far. After calling dfs
on our root node, ans
will contain the maximum length of the path we are looking for, and we return it as the solution.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
Solution Approach
The solution implements a recursive depth-first search approach, similar to finding the diameter of a binary tree (as suggested in the reference solution approach). Here's a more detailed breakdown of the implementation:
-
Recursive Depth-First Search (DFS):
- We define a nested recursive helper function
dfs
inside ourlongestUnivaluePath
method. This function is responsible for exploring the tree depth-first, starting from theroot
. - The purpose of
dfs
is to traverse the tree and calculate the longest univalue path for each node recursively.
- We define a nested recursive helper function
-
Global Variable for the Answer:
- We use a nonlocal variable
ans
which is declared before the nesteddfs
function and is used to keep track of the longest path we have found during the recursion.
- We use a nonlocal variable
-
Tracking the Current Node's Path:
- Inside
dfs
, we initially check if the currentroot
node isNone
. If it is, the function returns0
, as there is no path extending from a nonexistent node. - We then recursively call
dfs
for both theleft
andright
child nodes of the currentroot
.
- Inside
-
Path Extension Logic:
- We extend the path only if the child node has the same value as the current node. If
root.left
exists and its value is the same asroot.val
, we add1
to the value returned bydfs(root.left)
; otherwise, we reset it to0
. - Similarly, we do the same for
root.right
.
- We extend the path only if the child node has the same value as the current node. If
-
Updating the Longest Path (
ans
):- At each step, after computing the value of left and right univalue paths, we update our global variable
ans
with the sum of left and right paths if this sum represents a new maximum. It's crucial to recognize that the longest univalue path that passes through the current node is the sum of the longest univalue paths going down through its left and right children (provided the values match). - This step corresponds to potentially joining two paths together at the current
root
node to form a longer path.
- At each step, after computing the value of left and right univalue paths, we update our global variable
-
Returning the Best Unidirectional Path:
- Since we cannot include both the left and right paths in our final answer (as that would constitute a split, not a single path), we return the maximum of the two, again incremented by
1
for the current node if applicable.
- Since we cannot include both the left and right paths in our final answer (as that would constitute a split, not a single path), we return the maximum of the two, again incremented by
-
End of Recursion and Result:
- The recursion bottoms out when we hit
None
nodes, and it builds the solution as it unwinds the recursive calls. - Finally, the
longestUnivaluePath
method returns the value ofans
.
- The recursion bottoms out when we hit
Note that by defining the dfs
function within the longestUnivaluePath
method, we are able to use the nonlocal
keyword which allows us to modify the ans
variable inside the nested function. This is an example of using closure in Python to maintain the state between function calls.
The key algorithmic pattern here is recursion in tandem with a global variable to keep track of the optimal solution. The code uses a straightforward recursive DFS strategy tailored to track a specific condition—the nodes along a path have the same value.
By breaking down the problem into a series of recursive steps, each handling a local part of the tree around a single node, we are able to build the overall solution globally by gathering and combining the local answers.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider a small binary tree to illustrate the solution approach:
1 4 2 / \ 3 4 5 4 / \ \ 5 4 4 5
Now, let's walk through the algorithm on this example:
- We initiate the
longestUnivaluePath
with the root of the tree (value 4). - In our first call to the recursive
dfs
function, we examine the root having the value4
. - We recursively call
dfs
on the left and right children, which will return the longest univalue paths with the same value as these child nodes. The left child (value 4) and right child (value 5) calls are made.
For the left child (value 4):
- The
dfs
function is called with the left child, which is a node with value4
. - Similarly,
dfs
is called on its left and right children. Both have the value4
, so each child will contribute a value of1
to the path length (after thedfs
call). - No further calls to
dfs
are necessary down the leftmost branch as the children areNone
. The call for the left child of our current node (value 4) returns1
as the maximum from either side. - The call for the right child (also value 4) will also return
1
because its children areNone
. - Both children had the same value as the current node, so the total path length for this node is the sum of both children plus the current node, which is
1 + 1 = 2
. This value2
will be considered further up the tree.
For the right child (value 5):
- The
dfs
function is called with the right child, which is a node with value5
. - Its left child is
None
, and its right child has the same value,5
, so it will contribute1
. - No further
dfs
calls down this path are necessary because the right child of the right node isNone
. The returned path length is1
.
Back to the root:
- Now we return to the root node with value
4
. The left path provided a length of2
(obtained from the left child calls), and the right path provided a length of1
(obtained from the right child call). - We take the sum of both lengths since both children's values match with the root's value, so we get
2 + 1
. We update the global answerans
if3
is greater than the current value ofans
. - The
dfs
call at the root then needs to return the longest univalue path that includes the root node. So it chooses the maximum between the left and right path lengths, which is2
from the left, and returns2
.
After the root node's dfs
function is processed, our answer (ans
) holds the longest univalue path, which is 3
. This is the sum of the lengths from the left path and the right path passing through the root. Since we start counting from one node and end at another, considering the number of edges between the nodes, we have two edges, which represent the longest path, where all nodes share the same value.
The visualization of the longest univalue path is as follows:
1 4
2 /
3 4
4 /
5 4
So, the function longestUnivaluePath
finally returns the value 2
which is the length of the longest path with equal node values in the tree.
Solution Implementation
1class TreeNode:
2 # Initializer for the TreeNode class
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val
5 self.left = left
6 self.right = right
7
8class Solution:
9 def longestUnivaluePath(self, root: TreeNode) -> int:
10 # This helper function performs depth-first search on the binary tree
11 # to find the longest univalue path from the root node.
12 def dfs(node):
13 if node is None:
14 return 0
15
16 # Recursively find the longest path in the left and right subtree
17 left_path_length = dfs(node.left)
18 right_path_length = dfs(node.right)
19
20 # If the current node's value matches that of its left child,
21 # we can extend the univalue path by 1; otherwise, we reset to 0.
22 left_path = left_path_length + 1 if node.left and node.left.val == node.val else 0
23
24 # Similarly for the right child.
25 right_path = right_path_length + 1 if node.right and node.right.val == node.val else 0
26
27 # We use a nonlocal variable 'longest_path' to keep track of the
28 # longest univalue path found during the DFS.
29 nonlocal longest_path
30 longest_path = max(longest_path, left_path + right_path)
31
32 # Return the longest path from this node to its children that continues
33 # the univalue path (only the longer one of left or right can be part of the path).
34 return max(left_path, right_path)
35
36 longest_path = 0
37 dfs(root)
38 return longest_path
39
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 int value; // Node value
6 TreeNode left; // Left child
7 TreeNode right; // Right child
8
9 // Default constructor
10 TreeNode() {}
11
12 // Constructor with value
13 TreeNode(int value) { this.value = value; }
14
15 // Constructor with value, left child, and right child
16 TreeNode(int value, TreeNode left, TreeNode right) {
17 this.value = value;
18 this.left = left;
19 this.right = right;
20 }
21}
22
23class Solution {
24 private int longestPath; // To store the result of the longest univalue path
25
26 public int longestUnivaluePath(TreeNode root) {
27 longestPath = 0; // Initialize the longest path length to 0
28 depthFirstSearch(root); // Begin DFS from the root
29 return longestPath; // Return the maximum length found
30 }
31
32 // Helper method to perform DFS on each node
33 private int depthFirstSearch(TreeNode node) {
34 if (node == null) {
35 // If the node is null, there is no path
36 return 0;
37 }
38 // Recursively find the longest path in the left subtree
39 int leftPathLength = depthFirstSearch(node.left);
40 // Recursively find the longest path in the right subtree
41 int rightPathLength = depthFirstSearch(node.right);
42
43 // If the left child exists and has the same value, extend the left path
44 leftPathLength = (node.left != null && node.left.value == node.value) ? leftPathLength + 1 : 0;
45 // If the right child exists and has the same value, extend the right path
46 rightPathLength = (node.right != null && node.right.value == node.value) ? rightPathLength + 1 : 0;
47
48 // Update the longest path found so far considering both leftPath and rightPath
49 longestPath = Math.max(longestPath, leftPathLength + rightPathLength);
50
51 // The returned value should be the longest single side path (not combined) from this node
52 return Math.max(leftPathLength, rightPathLength);
53 }
54}
55
1// Definition for a binary tree node.
2struct TreeNode {
3 int val; // The value of the node.
4 TreeNode *left; // Pointer to the left child node.
5 TreeNode *right; // Pointer to the right child node.
6
7 // Constructor to initialize a node with no children.
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9
10 // Constructor to initialize a node with a value and no children.
11 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12
13 // Constructor to initialize a node with a value and left and right children.
14 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
15};
16
17class Solution {
18public:
19 int longestPath; // Stores the length of the longest univalue path.
20
21 // Public method to initiate the process and return the longest univalue path.
22 int longestUnivaluePath(TreeNode* root) {
23 longestPath = 0;
24 dfs(root);
25 return longestPath;
26 }
27
28private:
29 // Helper DFS method to compute the univalue path length for each subtree.
30 int dfs(TreeNode* node) {
31 if (!node) return 0; // Base case: if the node is null, return 0.
32
33 // Recursively find the longest univalue path in the left and right subtrees.
34 int leftPathLength = dfs(node->left);
35 int rightPathLength = dfs(node->right);
36
37 // If the left child exists and has the same value, increment leftPathLength.
38 leftPathLength = (node->left && node->left->val == node->val) ? leftPathLength + 1 : 0;
39
40 // If the right child exists and has the same value, increment rightPathLength.
41 rightPathLength = (node->right && node->right->val == node->val) ? rightPathLength + 1 : 0;
42
43 // Update the longestPath with the maximum value of itself and the sum of left and right paths.
44 longestPath = std::max(longestPath, leftPathLength + rightPathLength);
45
46 // Return the longer path of the two: either leftPathLength or rightPathLength.
47 return std::max(leftPathLength, rightPathLength);
48 }
49};
50
1// Define the structure for a binary tree node with numeric values
2interface TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6}
7
8/**
9 * Computes the length of the longest path where each node in the path has the same value.
10 * This path may or may not pass through the root.
11 *
12 * @param {TreeNode | null} root - The root node of the binary tree.
13 * @return {number} The length of the longest univalue path.
14 */
15function longestUnivaluePath(root: TreeNode | null): number {
16 // If the tree is empty, return zero as there are no paths.
17 if (root === null) {
18 return 0;
19 }
20
21 // Initialize the result variable to store the maximum path length found so far.
22 let result = 0;
23
24 /**
25 * Performs depth-first search on the binary tree to find the longest univalue path.
26 *
27 * @param {TreeNode | null} node - The current node being explored.
28 * @param {number} targetValue - The target value nodes in the path should have.
29 * @return {number} The length of the longest univalue path through the current node.
30 */
31 function dfs(node: TreeNode | null, targetValue: number): number {
32 // Base case: if the node is null, return zero as there is no path.
33 if (node === null) {
34 return 0;
35 }
36
37 // Recursively find the longest univalue path in the left subtree.
38 let leftPathLength = dfs(node.left, node.val);
39 // Recursively find the longest univalue path in the right subtree.
40 let rightPathLength = dfs(node.right, node.val);
41
42 // Update the result with the maximum path length by summing left and right paths if they are univalue.
43 result = Math.max(result, leftPathLength + rightPathLength);
44
45 // If the current node's value matches the target value,
46 // return the longest path length including the current node;
47 // otherwise, return zero as the path breaks here.
48 if (node.val === targetValue) {
49 return 1 + Math.max(leftPathLength, rightPathLength);
50 }
51 return 0;
52 }
53
54 // Start the depth-first search from the root.
55 dfs(root, root.val);
56
57 // The result contains the longest univalue path length.
58 return result;
59}
60
Time and Space Complexity
Time Complexity
The time complexity of the longestUnivaluePath
function is O(n)
where n
is the number of nodes in the binary tree. This is because the dfs
function is called once for every node in the tree, and each call to the dfs
function processes the current node independently of the other nodes. Since the algorithm must visit all nodes to determine the longest univalue path, it results in a linear time complexity relative to the number of nodes.
Space Complexity
The space complexity of the longestUnivaluePath
function is O(h)
where h
is the height of the tree. This is due to the recursive nature of the dfs
function, which results in a call stack proportional to the height of the tree in the worst case (e.g., the tree is skewed). For a balanced tree, the height h
would be log(n)
, leading to a space complexity of O(log(n))
. However, in the worst case (a skewed tree), the space complexity would be O(n)
, where n
is the total number of nodes.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.