Jobs

Interviews

Discussions

Binary Tree Paths

Easy

Apple

1 view

Topics:

TreesRecursion

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

A leaf is a node with no children.

For example:

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

Constraints:

The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100

Binary Tree Paths

Easy

Apple

1 view

Topics:

TreesRecursion

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

A leaf is a node with no children.

For example:

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

Constraints:

The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the binary tree? Can they be negative?
Can the tree be empty, or can a node have only one child? If so, what should the output be?
Should the paths be returned in any specific order?
By 'path' do you mean a sequence of nodes from the root to a leaf node, or can the path start and end at any node in the tree?
Is the tree guaranteed to be a binary search tree or just a binary tree?

Brute Force Solution

Approach

The goal is to find all possible routes from the top of a tree to its leaves. The brute force method explores every single path, writing it down as we go. We continue this exhaustive search until we've documented every possible path from the root to a leaf.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
From there, try going down every possible branch, one at a time.
As you go down a branch, write down the nodes you've visited along that path.
When you reach a leaf (a node with no further branches), you have found a complete path. Save this path.
Go back to the top and try a different branch to create a new path.
Continue exploring and recording paths in this way until you've exhausted every possible branch from the root to a leaf.

Code Implementation

def binary_tree_paths(root):
    all_paths = []

    def find_paths(node, current_path):
        if not node:
            return

        current_path.append(str(node.val))

        # Check if the current node is a leaf node.
        if not node.left and not node.right:
            all_paths.append("->".join(current_path))

        else:
            # Explore left subtree
            find_paths(node.left, current_path)

            # Explore right subtree
            find_paths(node.right, current_path)

        # Backtrack: remove the current node from the path
        current_path.pop()

    # Initiate path finding from the root
    find_paths(root, [])
    return all_paths

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once to construct the paths. In the worst-case scenario, we must traverse all n nodes of the tree. Because each node's data processing time is considered constant, the total time taken is proportional to n, leading to a time complexity of O(n). Note that while building each path might take time proportional to its length (at most n in the worst case of a skewed tree), we only visit each node once overall across all paths.

Space Complexity

O(N) – The algorithm explores each possible path from the root to a leaf, creating temporary paths to store the nodes visited along the way. In the worst-case scenario (e.g., a skewed tree), the maximum depth of recursion, and thus the length of the longest path stored, can be N, where N is the number of nodes in the tree. Therefore, the space used by the recursion stack and the path storage is proportional to N. This leads to a space complexity of O(N).

Optimal Solution

Approach

We need to find every possible route from the top of the tree to its endpoints. We can do this by keeping track of each route as we travel down the tree, adding to the route as we go. When we reach an endpoint, we save the complete route.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Create a path by writing down the value of the current tree node.
Move to the left tree node (if it exists) and add that value to the path.
Move to the right tree node (if it exists) and add that value to the path.
If we're at the end of a branch, meaning we can't go any further down either side, then we've found a complete path, so save it.
Go back up a step and explore the path we didn't take from that point.
Continue doing this until we've traveled down every possible branch, creating and saving each path.
The answer is the collection of all the paths we've saved.

Code Implementation

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

def binary_tree_paths(root):
    all_paths = []

    def get_paths(node, current_path):
        if not node:
            return

        current_path += str(node.value)

        # If it's a leaf, save the path and stop.
        if not node.left and not node.right:
            all_paths.append(current_path)
            return

        current_path += "->"

        # Explore the left subtree
        if node.left:
            get_paths(node.left, current_path)

        # Explore the right subtree
        if node.right:
            get_paths(node.right, current_path)

    get_paths(root, "")
    return all_paths

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once to construct all paths. In the worst-case scenario (a skewed tree), it still traverses all n nodes. Constructing each path takes time proportional to the depth of the node, which is bounded by n. However, the cumulative cost of building all paths remains proportional to n because each node contributes to one or more paths. Therefore, the time complexity is O(n), where n is the number of nodes in the binary tree.

Space Complexity

O(N) – The algorithm uses recursion to traverse the binary tree. In the worst-case scenario (a skewed tree), the recursion depth can reach N, where N is the number of nodes in the tree. Each recursive call adds a frame to the call stack, leading to O(N) space usage. Additionally, paths are constructed and stored, with each path potentially containing up to N nodes in a skewed tree, but since we are considering auxiliary space, we only count the space occupied by the call stack. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null root node	Return an empty list if the root is null as there are no paths.
Single node tree (root only)	Return a list containing the string representation of the root's value.
Large, balanced tree	Ensure the solution's space complexity, especially due to recursion or string concatenation, is acceptable and doesn't lead to stack overflow.
Highly unbalanced (skewed) tree (e.g., left-leaning or right-leaning)	Be mindful of stack depth in recursive solutions; an iterative approach might be preferred for extreme skewness to avoid stack overflow.
Tree with negative node values	The standard algorithm works correctly with negative values as the path construction is based on node traversal, not value comparisons.
Tree with zero node values	The standard algorithm works correctly with zero values as the path construction is based on node traversal, not value comparisons.
Very large integer node values approaching integer limits	String conversion of very large integers should be checked for potential overflow or formatting issues depending on the language used.
Deeply nested tree approaching system stack limits	Consider converting the recursive solution to an iterative one using a stack data structure to avoid exceeding call stack limits.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the binary tree? Can they be negative?
Can the tree be empty, or can a node have only one child? If so, what should the output be?
Should the paths be returned in any specific order?
By 'path' do you mean a sequence of nodes from the root to a leaf node, or can the path start and end at any node in the tree?
Is the tree guaranteed to be a binary search tree or just a binary tree?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
From there, try going down every possible branch, one at a time.
As you go down a branch, write down the nodes you've visited along that path.
When you reach a leaf (a node with no further branches), you have found a complete path. Save this path.
Go back to the top and try a different branch to create a new path.
Continue exploring and recording paths in this way until you've exhausted every possible branch from the root to a leaf.

Code Implementation

def binary_tree_paths(root):
    all_paths = []

    def find_paths(node, current_path):
        if not node:
            return

        current_path.append(str(node.val))

        # Check if the current node is a leaf node.
        if not node.left and not node.right:
            all_paths.append("->".join(current_path))

        else:
            # Explore left subtree
            find_paths(node.left, current_path)

            # Explore right subtree
            find_paths(node.right, current_path)

        # Backtrack: remove the current node from the path
        current_path.pop()

    # Initiate path finding from the root
    find_paths(root, [])
    return all_paths

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Create a path by writing down the value of the current tree node.
Move to the left tree node (if it exists) and add that value to the path.
Move to the right tree node (if it exists) and add that value to the path.
If we're at the end of a branch, meaning we can't go any further down either side, then we've found a complete path, so save it.
Go back up a step and explore the path we didn't take from that point.
Continue doing this until we've traveled down every possible branch, creating and saving each path.
The answer is the collection of all the paths we've saved.

Code Implementation

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

def binary_tree_paths(root):
    all_paths = []

    def get_paths(node, current_path):
        if not node:
            return

        current_path += str(node.value)

        # If it's a leaf, save the path and stop.
        if not node.left and not node.right:
            all_paths.append(current_path)
            return

        current_path += "->"

        # Explore the left subtree
        if node.left:
            get_paths(node.left, current_path)

        # Explore the right subtree
        if node.right:
            get_paths(node.right, current_path)

    get_paths(root, "")
    return all_paths

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return an empty list if the root is null as there are no paths.
Single node tree (root only)	Return a list containing the string representation of the root's value.
Large, balanced tree	Ensure the solution's space complexity, especially due to recursion or string concatenation, is acceptable and doesn't lead to stack overflow.
Highly unbalanced (skewed) tree (e.g., left-leaning or right-leaning)	Be mindful of stack depth in recursive solutions; an iterative approach might be preferred for extreme skewness to avoid stack overflow.
Tree with negative node values	The standard algorithm works correctly with negative values as the path construction is based on node traversal, not value comparisons.
Tree with zero node values	The standard algorithm works correctly with zero values as the path construction is based on node traversal, not value comparisons.
Very large integer node values approaching integer limits	String conversion of very large integers should be checked for potential overflow or formatting issues depending on the language used.
Deeply nested tree approaching system stack limits	Consider converting the recursive solution to an iterative one using a stack data structure to avoid exceeding call stack limits.