Root to Leaf Paths 🎯

Welcome to an exciting journey through the forest of data structures! Today, we're going to explore one of the most fascinating paths in this forest - the Root to Leaf Paths. This journey is perfect for both beginners and intermediates, so grab your compass and let's embark on this adventure! 🌳

Understanding the Forest 📝

Before we dive into the root-to-leaf paths, let's take a moment to familiarize ourselves with the forest we're in - a binary tree.

A binary tree is a tree in which each node has at most two children, often referred to as the left child and the right child.

markdown

             A
          /     \
         B         C
     /   \       /   \
    D   E     F   G   H

In this binary tree, A is the root, B, C, D, E, F, G, and H are the nodes, and the lines connecting them are the edges.

The Quest for Root to Leaf Paths 💡

Now that we know the forest, let's focus on the paths we're looking for - the root-to-leaf paths.

A root-to-leaf path is a path from the root to a leaf (a node without children) in a binary tree. Each edge in this path connects a parent node to its child.

Finding Root to Leaf Paths 📝

To find all the root-to-leaf paths in a binary tree, we can use a recursive approach. Here's a simple Python example:

python

def find_paths(node, path, result):
    if not node:
        return

    path.append(node.val)

    # If this node is a leaf, add the path to the result
    if not node.left and not node.right:
        result.append(path[:])

    # Traverse the left and right subtrees
    if node.left:
        find_paths(node.left, path, result)
    if node.right:
        find_paths(node.right, path, result)

    # Backtrack when returning from a subtree
    path.pop()

In this example, we define a helper function find_paths that takes the current node, the current path, and a list to store all the root-to-leaf paths. The function works by:

Adding the current node's value to the path.
Checking if the current node is a leaf. If it is, we append the current path to the result.
Recursively traversing the left and right subtrees, adding their root-to-leaf paths to the result.
Backtracking by removing the last added node from the path before returning from the subtree.

Practice Time 📝

Now, let's test your understanding with a small quiz.

That's all for today! I hope you enjoyed exploring the root-to-leaf paths in a binary tree. Remember, practice makes perfect, so keep coding and have fun! 😃