algoadvance

Leetcode 687. Longest Univalue Path

Problem Statement

Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.

Clarifying Questions

1. Tree Structure: Can the tree nodes have negative values, or are they strictly non-negative?
   • Assumed non-negative.
2. Path Characteristics: Is the path strictly limited to parent-child connections, or can it form other structures (like subtrees)?
   • The path is limited to parent-child connections.
3. Tree Size: Is there a limit on the size of the tree (number of nodes)?
   • We’ll assume the tree can be of any size that fits into memory.

Strategy

1. DFS Traversal: Use Depth-First Search (DFS) to explore each node in the tree.
2. Postorder Traversal: Recursively calculate the longest path for each subtree. After processing left and right children, determine the longest path that can be formed including the current node.
3. Same Value Check: For each node, check if the value is the same as its left or right child to count the path length.
4. Global Maximum: Maintain a global variable to track the maximum path length found.
5. Return Values: For each node, return the longest path through the node that extends upwards to its parent.

Code

class Solution {
    private int maxLength = 0;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return maxLength;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftLength = dfs(node.left);
        int rightLength = dfs(node.right);

        int leftPath = 0, rightPath = 0;

        // Check if left child exists and has the same value as current node
        if (node.left != null && node.left.val == node.val) {
            leftPath = leftLength + 1;
        }

        // Check if right child exists and has the same value as current node
        if (node.right != null && node.right.val == node.val) {
            rightPath = rightLength + 1;
        }

        // Update the global maxLength
        maxLength = Math.max(maxLength, leftPath + rightPath);

        // Return the max length of the path extending from current node to its parent
        return Math.max(leftPath, rightPath);
    }
}

Time Complexity

• Time Complexity: (O(n))
  • We visit each node exactly once.
• Space Complexity: (O(h)), where (h) is the height of the tree.
  • This is the space required for the call stack during the recursive DFS traversal.

This code ensures that we find the longest univalue path in the given binary tree efficiently by leveraging the properties of DFS and maintaining a global state to track the longest path length.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?