Leetcode 257. Binary Tree Paths

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.

Approach 1:


class Solution {
    public List binaryTreePaths(final TreeNode root) {
        final List result = new ArrayList<>();

        helper(result, new StringBuilder(), root);

        return result;
    }

    private void helper(final List result, final StringBuilder sb, final TreeNode root) {
        final int tmp = sb.length();

        if (root.left == null && root.right == null) {
            sb.append(root.val);
            result.add(sb.toString());
        } else {
            sb.append(root.val);
            sb.append("->");

            if (root.right != null)
                helper(result, sb, root.right);

            if (root.left != null)
                helper(result, sb, root.left);
        }

        sb.setLength(sb.length() - (sb.length() - tmp));
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Introduction

The "Binary Tree Paths" problem involves finding all root-to-leaf paths in a binary tree. A root-to-leaf path is a path that starts from the root and ends at a leaf node (a node with no children). Each path must be represented as a string, where the node values are separated by an arrow (e.g., "5->4->11->2").

Problem Statement

Given the root of a binary tree, return all root-to-leaf paths in the tree. A root-to-leaf path is defined as a path starting at the root node and ending at a leaf node. The path should be represented as a string, with node values separated by "->".

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

The tree node structure is given above. The goal is to return all root-to-leaf paths as strings where each path represents the sequence of nodes in the path, separated by an arrow ("->").

Approach

To solve this problem, we can use depth-first search (DFS) to explore all root-to-leaf paths. At each node, we append the current node’s value to the path string. When we reach a leaf node, we add the path to the result list. After reaching a leaf, we backtrack and explore other potential paths.

Start by performing a DFS traversal from the root node.
At each node, append its value to the current path string.
If a leaf node is reached, add the current path to the result list.
Recursively explore the left and right subtrees of each node.
Backtrack by removing the last node from the current path when exploring other paths.

Algorithm

The algorithm follows these steps:

Define a helper function to perform a DFS traversal.
At each node, append the current node’s value to the current path string.
If the node is a leaf, add the current path to the result list.
Recursively explore both the left and right children of the node.
Backtrack by removing the current node’s value from the path when returning from the child nodes.

This approach ensures that all root-to-leaf paths are explored and represented as strings.

Example

Consider the following binary tree:

In this example, the following root-to-leaf paths exist: - Path 1: "1->2->4" - Path 2: "1->2->5" - Path 3: "1->3->6"

Therefore, the solution should return the following list of paths: - ["1->2->4", "1->2->5", "1->3->6"]

Code Implementation

Below is the Python implementation of the algorithm to find all root-to-leaf paths:

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

def binaryTreePaths(root):
    result = []
    
    def dfs(node, current_path):
        if not node:
            return
        
        # Add the current node's value to the path
        current_path += str(node.val)
        
        # If it's a leaf node, add the path to the result
        if not node.left and not node.right:
            result.append(current_path)
        else:
            # Otherwise, continue DFS on the left and right subtrees
            current_path += "->"
            dfs(node.left, current_path)
            dfs(node.right, current_path)
    
    # Start the DFS traversal from the root
    dfs(root, "")
    return result

In this code: - The `binaryTreePaths` function initializes the result list and calls the `dfs` helper function to explore all paths. - The `dfs` function recursively explores the left and right subtrees of the current node. At each node, it appends the current node’s value to the path string. - When a leaf node is reached, the current path is added to the result list. - The function backtracks by adding the arrow ("->") to the path string when continuing the DFS traversal.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. In the worst case, we must visit each node once to form the root-to-leaf paths.

The space complexity is O(h), where h is the height of the tree. This space is used by the recursion stack during the DFS traversal. In the worst case, the height of the tree is O(n) (for a skewed tree), and in the best case, it is O(log n) (for a balanced tree).

Conclusion

The "Binary Tree Paths" problem is a good example of using depth-first search (DFS) to explore all root-to-leaf paths in a binary tree and represent those paths as strings. By using recursion, we can efficiently find all paths from the root to the leaves and return them in the desired format.