DSA Visualizations | Hello Interview

Longest Univalue Path

DESCRIPTION (credit 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. Return the number of edges on that path, not the number of nodes.

EXAMPLES

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.

Run your code to see results here

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.

Both the leaf nodes shown above return 0 to its parent node.

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.

Because the parent (4) has a value equal to its left child, the length of the longest univalue path through node 4 is 1.

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:

Both the leaf nodes shown above return 0 to its parent node.

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.

Longest univalue path through 4: 2 + 0 + 0

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

class Solution:
    def longestUnivaluePath(self, root):
        max_length = 0
        
        def dfs(node):
            nonlocal max_length
            if not node:
                return 0
            
            left_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 node
            if node.left and node.left.val == node.val:
                left_arrow = left_length + 1
            if 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 node
            max_length = max(max_length, left_arrow + right_arrow)
            return max(left_arrow, right_arrow)
        
        dfs(root)
        return max_length

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

Next: Overview

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Path Sum II

Overview

Longest Univalue Path

DESCRIPTION (credit Leetcode.com)

EXAMPLES

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.

Run your code to see results here

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.

Calculating the Longest Univalue Path at a 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.

Both the leaf nodes shown above return 0 to its parent node.

Those values are received by the parent node, which uses them to calculate the longest univalue path that passes through its node.

Because the parent (4) has a value equal to its left child, the length of the longest univalue path through node 4 is 1.

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:

Both the leaf nodes shown above return 0 to its parent node.

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.

Longest univalue path through 4: 2 + 0 + 0

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.

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.

Then, we can update the global variable max_length with the length of the longest univalue path that goes through the current node.

Solution

class Solution:
    def longestUnivaluePath(self, root):
        max_length = 0
        
        def dfs(node):
            nonlocal max_length
            if not node:
                return 0
            
            left_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 node
            if node.left and node.left.val == node.val:
                left_arrow = left_length + 1
            if 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 node
            max_length = max(max_length, left_arrow + right_arrow)
            return max(left_arrow, right_arrow)
        
        dfs(root)
        return max_length

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.

Next: Overview

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103