Finding the largest value in each tree row
Tags: leetcode, algorithms
Published: 2023-10-24 23:13:03

---
title: Finding the largest value in each tree row
published: true
description:
tags: leetcode, algorithms
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-10-24 20:46 +0000
---

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:

![binary tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/odj1lh4a4mcbocb1hje6.png)


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:

```python
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](https://en.wikipedia.org/wiki/Stack_(abstract_data_type))

```python
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](https://en.wikipedia.org/wiki/Queue_(abstract_data_type))

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]`.

```python
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:

![binary tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/skdgscrn48us3vzhggeg.png)

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:

```python
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.