Solving "Binary Tree Paths"

Today I'm going to explain how to solve "Binary Tree Paths" problem.

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:

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. 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 algorithm to traverse the tree;
• In each 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:

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.

if not root:
    return []

DFS

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

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

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.

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.

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.

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.