687. Longest Univalue Path

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

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.

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:

  1. If the node is null, we cannot extend the path, so we return zero.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

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:

  1. Recursive Depth-First Search (DFS):

    • We define a nested recursive helper function dfs inside our longestUnivaluePath method. This function is responsible for exploring the tree depth-first, starting from the root.
    • The purpose of dfs is to traverse the tree and calculate the longest univalue path for each node recursively.

  2. Global Variable for the Answer:

    • We use a nonlocal variable ans which is declared before the nested dfs function and is used to keep track of the longest path we have found during the recursion.

  3. Tracking the Current Node's Path:

    • Inside dfs, we initially check if the current root node is None. If it is, the function returns 0, as there is no path extending from a nonexistent node.
    • We then recursively call dfs for both the left and right child nodes of the current root.

  4. 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 as root.val, we add 1 to the value returned by dfs(root.left); otherwise, we reset it to 0.
    • Similarly, we do the same for root.right.

  5. 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.

  6. 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.

  7. 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 of ans.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example 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:

  1. We initiate the longestUnivaluePath with the root of the tree (value 4).
  2. In our first call to the recursive dfs function, we examine the root having the value 4.
  3. 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):

  1. The dfs function is called with the left child, which is a node with value 4.
  2. Similarly, dfs is called on its left and right children. Both have the value 4, so each child will contribute a value of 1 to the path length (after the dfs call).
  3. No further calls to dfs are necessary down the leftmost branch as the children are None. The call for the left child of our current node (value 4) returns 1 as the maximum from either side.
  4. The call for the right child (also value 4) will also return 1 because its children are None.
  5. 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 value 2 will be considered further up the tree.

For the right child (value 5):

  1. The dfs function is called with the right child, which is a node with value 5.
  2. Its left child is None, and its right child has the same value, 5, so it will contribute 1.
  3. No further dfs calls down this path are necessary because the right child of the right node is None. The returned path length is 1.

Back to the root:

  1. Now we return to the root node with value 4. The left path provided a length of 2 (obtained from the left child calls), and the right path provided a length of 1 (obtained from the right child call).
  2. 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 answer ans if 3 is greater than the current value of ans.
  3. 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 is 2 from the left, and returns 2.

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
Not Sure What to Study? Take the 2-min Quiz๏ผš

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Recommended Readings

Everything About Trees

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

DFS Fundamentals

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

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 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 ๐Ÿ‘จโ€๐Ÿซ