Jobs

Interviews

Discussions

Find Largest Value in Each Tree Row

Medium

Asked by:

More companies

83 views

Topics:

TreesRecursion

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:

Input: root = [1,2,3]
Output: [1,3]

Constraints:

The number of nodes in the tree will be in the range [0, 10⁴].
-2³¹ <= Node.val <= 2³¹ - 1

Try coding it in LeetCode

Find Largest Value in Each Tree Row

Medium

Asked by:

83 views

Topics:

TreesRecursion

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:

Input: root = [1,2,3]
Output: [1,3]

Constraints:

The number of nodes in the tree will be in the range [0, 10⁴].
-2³¹ <= Node.val <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the tree? Could they be negative?
Can the tree be empty or contain only a single node?
What should be the return type? Should it be a list of integers, and should the order correspond to the level order traversal?
If a row is empty (which shouldn't happen with a proper tree, but just in case), what should I return for that row's largest value? Should I return null/None or skip it?
Is the tree guaranteed to be a valid binary tree, or could there be cycles or disconnected nodes?

Brute Force Solution

Approach

The goal is to find the biggest number in each horizontal level of a tree structure. A brute force approach visits every number in the tree, level by level, to find the largest one on each level.

Here's how the algorithm would work step-by-step:

Start by looking at the very top level of the tree.
Find the largest value on that level and remember it.
Move down to the next level.
Again, find the largest value on this new level and remember it.
Keep doing this for each level of the tree, one level at a time.
At the end, you'll have a list of the largest values, one for each level of the tree.

Code Implementation

def find_largest_value_in_each_tree_row_brute_force(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        level_size = len(queue)
        maximum_value_for_current_level = float('-inf')

        # Iterate through all nodes on the current level
        for _ in range(level_size):
            current_node = queue.pop(0)

            # Update the maximum value seen so far
            maximum_value_for_current_level = max(maximum_value_for_current_level, current_node.val)

            if current_node.left:
                queue.append(current_node.left)

            if current_node.right:
                queue.append(current_node.right)

        # Store maximum value for the current level
        result.append(maximum_value_for_current_level)

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the tree exactly once to determine the largest value at each level. Therefore, the time complexity is directly proportional to the number of nodes in the tree, which we denote as 'n'. The level-by-level traversal ensures that each node is processed only once. Consequently, the algorithm performs a constant amount of work for each of the n nodes, leading to a linear time complexity of O(n).

Space Complexity

O(W) – The provided approach relies on level-order traversal, implicitly using a queue to store nodes at each level. In the worst-case scenario, the queue might hold all nodes of the widest level of the tree. Thus, the auxiliary space is determined by the maximum width (W) of the tree, where N represents the total number of nodes in the tree. This queue is the primary consumer of space, enabling the level-by-level processing. Therefore, the space complexity is O(W).

Optimal Solution

Approach

The task is to find the largest number in each level (row) of a tree. We can efficiently solve this by exploring the tree level by level, keeping track of the largest value we encounter at each level as we go.

Here's how the algorithm would work step-by-step:

Imagine organizing the tree into distinct levels, like floors in a building.
Start at the very top level (the root of the tree).
For each level, look at every number on that level.
Keep track of the biggest number you see at that particular level.
Once you have looked at all numbers on a level, record the biggest number you found.
Move down to the next level and repeat the process until you've processed every level of the tree.
The list of biggest numbers you recorded, one for each level, is the answer.

Code Implementation

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_largest_value_in_each_tree_row(root):
    if not root:
        return []

    largest_values_in_each_row = []
    nodes_to_visit = deque([root])

    while nodes_to_visit:
        # Keep track of max value for
        # the current level
        current_level_size = len(nodes_to_visit)
        maximum_value_for_level = float('-inf')

        for _ in range(current_level_size):
            current_node = nodes_to_visit.popleft()
            maximum_value_for_level = max(maximum_value_for_level, current_node.val)

            if current_node.left:
                nodes_to_visit.append(current_node.left)

            if current_node.right:
                nodes_to_visit.append(current_node.right)

        # Append the maximum value 
        # after visiting all nodes
        largest_values_in_each_row.append(maximum_value_for_level)

    return largest_values_in_each_row

Big(O) Analysis

Time Complexity

O(n) – The provided approach traverses the binary tree level by level, visiting each node exactly once. The number of nodes in the tree is denoted by 'n'. Since we perform a constant amount of work (comparing and updating the maximum value) for each node, the overall time complexity is directly proportional to the number of nodes. Therefore, the time complexity is O(n).

Space Complexity

O(W) – The algorithm explores the tree level by level, and the dominant space usage comes from the queue or similar data structure used to hold the nodes at each level during the breadth-first traversal. In the worst-case scenario, the queue might contain all nodes at the widest level of the tree. Therefore, the auxiliary space complexity is determined by the maximum width (W) of the tree, as the queue needs to store, at most, all nodes on that level. Consequently, the space complexity is O(W), where W is the maximum width of the tree. If the tree is balanced, W would be approximately N/2, which is still O(N). However, in the general case, especially for unbalanced trees, it's more accurate to express it as O(W).

Edge Cases

Case	How to Handle
Null or Empty Tree	Return an empty list if the root is null, as there are no rows to process.
Tree with only a root node	Return a list containing only the root node's value, as this is the only row.
Tree with skewed distribution (e.g., heavily unbalanced left or right)	The solution should handle unbalanced trees correctly as the level-order traversal will process all nodes regardless of the tree's structure.
Tree with all nodes having identical values	The algorithm will still correctly find the largest value for each row, as all values are the same.
Tree with negative values	The algorithm will function correctly with negative values, comparing and tracking the largest value within each row, handling negative values properly.
Large tree to test scalability	Verify the breadth-first search approach scales adequately for larger trees, considering memory usage and time complexity.
Integer overflow when comparing very large node values	Ensure the comparison operation and data type used to store node values (e.g., int) are adequate to prevent potential integer overflows, possibly using long if needed.
Tree with extreme boundary integer values (Integer.MAX_VALUE, Integer.MIN_VALUE)	The comparison logic must correctly handle the cases where node values are at the extreme boundaries of the integer range, ensuring no unexpected behavior during the largest value determination.

Null or Empty Tree

How to Handle:

Return an empty list if the root is null, as there are no rows to process.

Tree with only a root node

How to Handle:

Return a list containing only the root node's value, as this is the only row.

Tree with skewed distribution (e.g., heavily unbalanced left or right)

How to Handle:

The solution should handle unbalanced trees correctly as the level-order traversal will process all nodes regardless of the tree's structure.

Tree with all nodes having identical values

How to Handle:

The algorithm will still correctly find the largest value for each row, as all values are the same.

Tree with negative values

How to Handle:

The algorithm will function correctly with negative values, comparing and tracking the largest value within each row, handling negative values properly.

Large tree to test scalability

How to Handle:

Verify the breadth-first search approach scales adequately for larger trees, considering memory usage and time complexity.

Integer overflow when comparing very large node values

How to Handle:

Ensure the comparison operation and data type used to store node values (e.g., int) are adequate to prevent potential integer overflows, possibly using long if needed.

Tree with extreme boundary integer values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

The comparison logic must correctly handle the cases where node values are at the extreme boundaries of the integer range, ensuring no unexpected behavior during the largest value determination.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the tree? Could they be negative?
Can the tree be empty or contain only a single node?
What should be the return type? Should it be a list of integers, and should the order correspond to the level order traversal?
If a row is empty (which shouldn't happen with a proper tree, but just in case), what should I return for that row's largest value? Should I return null/None or skip it?
Is the tree guaranteed to be a valid binary tree, or could there be cycles or disconnected nodes?

Brute Force Solution

Approach

The goal is to find the biggest number in each horizontal level of a tree structure. A brute force approach visits every number in the tree, level by level, to find the largest one on each level.

Here's how the algorithm would work step-by-step:

Start by looking at the very top level of the tree.
Find the largest value on that level and remember it.
Move down to the next level.
Again, find the largest value on this new level and remember it.
Keep doing this for each level of the tree, one level at a time.
At the end, you'll have a list of the largest values, one for each level of the tree.

Code Implementation

def find_largest_value_in_each_tree_row_brute_force(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        level_size = len(queue)
        maximum_value_for_current_level = float('-inf')

        # Iterate through all nodes on the current level
        for _ in range(level_size):
            current_node = queue.pop(0)

            # Update the maximum value seen so far
            maximum_value_for_current_level = max(maximum_value_for_current_level, current_node.val)

            if current_node.left:
                queue.append(current_node.left)

            if current_node.right:
                queue.append(current_node.right)

        # Store maximum value for the current level
        result.append(maximum_value_for_current_level)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine organizing the tree into distinct levels, like floors in a building.
Start at the very top level (the root of the tree).
For each level, look at every number on that level.
Keep track of the biggest number you see at that particular level.
Once you have looked at all numbers on a level, record the biggest number you found.
Move down to the next level and repeat the process until you've processed every level of the tree.
The list of biggest numbers you recorded, one for each level, is the answer.

Code Implementation

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_largest_value_in_each_tree_row(root):
    if not root:
        return []

    largest_values_in_each_row = []
    nodes_to_visit = deque([root])

    while nodes_to_visit:
        # Keep track of max value for
        # the current level
        current_level_size = len(nodes_to_visit)
        maximum_value_for_level = float('-inf')

        for _ in range(current_level_size):
            current_node = nodes_to_visit.popleft()
            maximum_value_for_level = max(maximum_value_for_level, current_node.val)

            if current_node.left:
                nodes_to_visit.append(current_node.left)

            if current_node.right:
                nodes_to_visit.append(current_node.right)

        # Append the maximum value 
        # after visiting all nodes
        largest_values_in_each_row.append(maximum_value_for_level)

    return largest_values_in_each_row

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Tree	Return an empty list if the root is null, as there are no rows to process.
Tree with only a root node	Return a list containing only the root node's value, as this is the only row.
Tree with skewed distribution (e.g., heavily unbalanced left or right)	The solution should handle unbalanced trees correctly as the level-order traversal will process all nodes regardless of the tree's structure.
Tree with all nodes having identical values	The algorithm will still correctly find the largest value for each row, as all values are the same.
Tree with negative values	The algorithm will function correctly with negative values, comparing and tracking the largest value within each row, handling negative values properly.
Large tree to test scalability	Verify the breadth-first search approach scales adequately for larger trees, considering memory usage and time complexity.
Integer overflow when comparing very large node values	Ensure the comparison operation and data type used to store node values (e.g., int) are adequate to prevent potential integer overflows, possibly using long if needed.
Tree with extreme boundary integer values (Integer.MAX_VALUE, Integer.MIN_VALUE)	The comparison logic must correctly handle the cases where node values are at the extreme boundaries of the integer range, ensuring no unexpected behavior during the largest value determination.

Null or Empty Tree

How to Handle:

Return an empty list if the root is null, as there are no rows to process.

Tree with only a root node

How to Handle:

Return a list containing only the root node's value, as this is the only row.

Tree with skewed distribution (e.g., heavily unbalanced left or right)

How to Handle:

The solution should handle unbalanced trees correctly as the level-order traversal will process all nodes regardless of the tree's structure.

Tree with all nodes having identical values

How to Handle:

The algorithm will still correctly find the largest value for each row, as all values are the same.

Tree with negative values

How to Handle:

The algorithm will function correctly with negative values, comparing and tracking the largest value within each row, handling negative values properly.

Large tree to test scalability

How to Handle:

Verify the breadth-first search approach scales adequately for larger trees, considering memory usage and time complexity.

Integer overflow when comparing very large node values

How to Handle:

Ensure the comparison operation and data type used to store node values (e.g., int) are adequate to prevent potential integer overflows, possibly using long if needed.

Tree with extreme boundary integer values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

The comparison logic must correctly handle the cases where node values are at the extreme boundaries of the integer range, ensuring no unexpected behavior during the largest value determination.