Finding the largest value in each tree row

#leetcode #algorithms

Recently, a friend sent me an intriguing challenge: finding the largest value in each row of a binary tree. It is a hard but rewarding problem to solve. Understanding how to navigate data structures is crucial.

This tree is a binary tree. In this post we will understand what is a binary tree and how to solve the proposed problem.

What is a binary tree?

A binary tree is a tree formed by nodes. A tree might have zero nodes, or just one. The first node of a tree is called root, and the last one is called leaf. A binary tree, just like a real tree, might have many branches, known as children. Children are nodes with parents, and leaves are nodes without children. Every node might have zero, one or two children.

Let's visualize it:

Every circle in the diagram above represents a node. A node is composed by the following attributes:

Value (a.k.a key)
Left node
Right node

The binary in binary tree means you can go to either left or right. If you could represent a node using Python, you would end up having the following class:

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

Can you see how the Node class compares to the visual representation of a node?

Finding the largest value in each tree row

Looking at the tree, we know that the largest values are: 1, 3 and 7.

We could traverse every row of the tree, save every largest value in a list and return it in the end. But finding the largest value in each row is not an easy task.

Notice we just used the word traverse. Traversing is the act of iterating over the nodes of the tree. We can do it using two techniques: depth first search (DFS) and breadth first search (BFS).

Let's explore both techniques in detail:

Depth first search

In depth first search, you find a node in the tree and keep traversing the tree in that direction to the end (leaves). To implement this technique, we will need to use a stack

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

    stack = [root]
    values = []

    while stack:
        curr_node = stack.pop()
        values.append(curr_node.val)

        if curr_node.right:
            stack.append(curr_node.right)

        if curr_node.left:
            stack.append(curr_node.left)

    return values

Since trees might be empty (or have no nodes), we first check if the root node is present before proceeding. Otherwise we add the root to the stack and traverse the tree until this stack is not empty.

Every round of the while loop we add the value of the current node to the list and add the left and right nodes to the stack if they exist.

First we add root (1) value to list
Then we find a right node (3) and add it to the stack
We also found a left node (2) and add it to the stack

Ok, now it is one of the most important parts: why are we adding the right node first?

It is very common to traverse a binary tree from left to right. Since we are using a stack, we always pop the last element. Our stack looks like this in the first iteration: [right, left]
If we pop from this stack, we always get the left position before right.

Breadth first search

In breadth first search we visit every left and right node of the tree in the same iteration - this is why it has breadth in the name.

We use this technique when we want to traverse the binary tree by row.

The code is very similar to the depth first search, except we use a queue

Since we want to iterate each row, we use a queue and the popleft function - it pops the first element of the structure.
Imagine we have the following queue: [1, 10, 20, 30]. When we perform a popleft operation, the queue becomes [10, 20, 30].

from collections import deque

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

    queue = deque([root])
    values = []

    while queue:
        curr_node = queue.popleft()
        values.append(curr_node.val)

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

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

    return values

First we add root (1) value to list
Then we find a left node (2) and add it to the queue
We also found a right node (3) and add it to the queue
Then we pop left the queue and we get the node with value 2 and add it to the list, it is now [1, 2]
And we, again, add the left and right nodes to the queue
But we still have the 3 in the queue. Next iteration we will append it to the list, and so on

Solving the problem

Which algorithm you think should be used to get the largest value from each row of the tree? Think about the tree below:

If we use depth first search, we will get all the values in a vertical way, right? In a depth first traversal, we move down the tree before considering siblings. But when finding the largest value in a row, we need to consider all nodes at the same depth before moving deeper, which aligns more with a horizontal traversal.

What about breadht first search? It seems the right technique.

Let's implement this, but first we will reason about the steps:

Create a queue and add the root to it
While we have elements in the queue we:
- Determine the current size of the queue, representing the number of nodes in the current row
- And iterate N times to get all the values from the row
- For each node in the current row, compare its value with the current maximum value (initialized as negative infinity).
- Compare and define the new max value
- Every time we end this iteration, we add the max value to the list of largest values

And the code is as follows:

from collections import deque

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

    queue = deque([root])
    largest = []

    while queue:
        size = len(queue)
        max_val = float("-inf")

        for i in range(size):
            curr_node = queue.popleft()

            if curr_node.val > max_val:
                max_val = curr_node.val

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

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

        largest.append(max_val)

    return largest

For the provided example tree, this code will return the list [1, 3, 9]

Solving these challenges is a matter of reading and practicing. With practice, choosing the right data structures and techniques for a given problem becomes more and more intuitive.