Solving "Binary Tree Paths"
Tags: dsa, leetcode, binarytree
Published: 2023-12-23 16:35:20

---
title: Solving "Binary Tree Paths"
published: true
description:
tags: dsa, leetcode, binarytree
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bomxdgmdc7d4lrigxul8.png
# Use a ratio of 100:42 for best results.
# published_at: 2023-12-20 01:10 +0000
---

Today I'm going to explain how to solve ["Binary Tree Paths" problem](https://leetcode.com/problems/binary-tree-paths/).

> Given the root of a binary tree, return all root-to-leaf paths in any order.

> A leaf is a node with no children.

A *binary tree* is a data structure characterized by **nodes**, each having either none or a maximum of two children: left and right. Each connection between nodes is called an **edge**, and the paths from the **root** to the **leaves** are simple known as **path**. 

Take a look at the image below as an example of a binary tree used in the problem. It illustrates a binary tree and its components:

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

For this problem, we need to identify and return a list of all the paths in any order.

```
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
```

In the example, there are two paths, both starting from the root and extending to the leaf nodes.

A leaf node is one that has no children. In this tree, numbers 5 and 3 are leaves as they have no outgoing connections.

How do we traverse this binary tree, discover the paths, and return them as the challenge requires?

## Reasoning

First, let's explore how we might approach this without any specific strategy or computational methods. Initially, you start from the root and follow each path to its end, choosing at each step either left or right. You note down each path on paper and proceed to the next until all paths are explored.

With this intuitive approach in mind, let's transition to formulating the algorithm in Python.

### Traversing

Understanding how to traverse the binary tree is a crucial part of the algorithm. There are two primary methods: depth-first (DFS) and breadth-first (BFS) search.

DFS is employed when you need to explore one branch of the tree thoroughly before [backtraking](https://en.wikipedia.org/wiki/Backtracking). On the other hand, BFS is utilized when you need to visit each level of the tree sequentially before backtracking.

## Writing the algorithm

This challenge, although considered easy, contains nuances especially for those new to binary trees and traversal methods.

* Use [depth-first search](https://en.wikipedia.org/wiki/Depth-first_search) algorithm to traverse the tree;
* In each [recursion](https://en.wikipedia.org/wiki/Recursion) call, concatenate the current path to the path passed in the initial call;
* As you move left and right, continue concatenating this path with an arrow;
* The recursion base happens upon encountering a leaf node.

### Why recursion?

Recursion is particularly suitable for problems involving binary tree due to its capability to handle a problem one step at a time. In a binary tree, each node often branches into two smaller subtrees (if they exist), which reminds us of step-by-step approach added to the call stack.

* No need to maintain a stack to traverse the tree;
* No need to implement a branching and backtracking mechanism - recursion handles this for us;
* Recursion and branching walk side-by-side.

## Coding

Here is the Python code to solve it:


```python
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []

        paths = []

        def dfs(node, path):
            if not node:
                return

            path += str(node.val)

            if not node.left and not node.right:
                paths.append(path)
                return

            if node.left:
                dfs(node.left, path + "->")

            if node.right:
                dfs(node.right, path + "->")

        dfs(root, "")

        return paths
```

Let's check what this code does in details.

**Base case**: we handle empty trees as they are valid binary trees. If there is no root (root is `None`), we return immediately.

```python
if not root:
    return []
```

### DFS

Our main call starts the recursive function from the root with an empty variable for the path.

```python
dfs(root, "")
```

**Base case**: this check is similar to our initial base case. For instance, after examining node 5, we see that both left and right are `None`, signaling the end of this path. Subsequently, each of these recursive calls starts unwinding the stack (backtracking).

```python
if not node: 
    return
```

**Path building**: here, we concatenate the current node's value to the path. This step is crucial as it builds the representation (a string) of the path from the root to the current node.

```python
path += str(node.val)
```

**Reaching the path's end**: a leaf node is defined as one without children. Upon finding a leaf, we append the path to our list of paths and return, allowing other recursive calls to execute.

```python
if not node.left and not node.right:
    paths.append(path)
    return
```

**Recursive calls**: if the current node has a left child, we call `dfs` recursively on the left child. The right node follows the very same process.

```python
if node.left:
    dfs(node.left, path + "->")

if node.right:
    dfs(node.right, path + "->")
```

## Time and space complexity

When discussing **time complexity** in our solution, we observe that for each node in the binary tree, a string concatenation operation is performed. In Python, strings are *immutable*, each concatenation results in the creation of a new string. This leads to an `O(N²)` operation at each node, where *N* represents the number of nodes in the tree.

As for **space complexity**, it is primarily impacted by the creation of multiple string objects resulting from these concatenations (`O(N)`).

**We can do better!**

One of the pain points of our solution is string concatenation. In Python, strings are **immutable**, so everytime you concatenate a string, it creates a new string including the content of both strings.

> Understanding the nuances of the programming language in use is vital, as different languages handle string concatenation differently.

### Challenge for the reader

Your challenge is to modify the code to avoid string concatenation. After making these changes, evaluate the performance of the revised approach in terms of time and space complexity. Share your findings here in the comments section.