algoadvance

Leetcode 257. Binary Tree Paths

Problem Statement

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

A leaf is a node with no children.

Clarifying Questions

1. What is the expected input and output?
   • Input: A binary tree root node.
   • Output: A list of strings, where each string represents a path from the root to a leaf.
2. What should be the format of the paths?
   • Each path should be represented as a string with node values separated by “->”. For instance, “1->2->5”.
3. Can the binary tree be empty?
   • Yes, if the tree is empty, the output should be an empty list.
4. Can the node values be negative or only positive integers?
   • Node values can be any integers.

Strategy

1. Depth-first Search (DFS):
   • Use DFS to traverse the binary tree.
   • Maintain a path list starting from the root.
   • When a leaf node is reached, convert the current path to the string format and add it to the result list.
   • Recursively explore the left and right children.
2. Base Case:
   • If the node is null, return immediately.
3. Leaf Node Detection:
   • A node is a leaf if both its left and right children are null.
4. Path Construction:
   • Append the current node’s value to the path.
   • Convert the path to the required string format when a leaf is reached.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) {
            return paths;
        }
        constructPaths(root, "", paths);
        return paths;
    }

    private void constructPaths(TreeNode node, String path, List<String> paths) {
        if (node != null) {
            path += Integer.toString(node.val);
            if (node.left == null && node.right == null) { // It's a leaf
                paths.add(path); // Add the path to the list
            } else {
                path += "->"; // Prepare for the next node
                if (node.left != null) {
                    constructPaths(node.left, path, paths);
                }
                if (node.right != null) {
                    constructPaths(node.right, path, paths);
                }
            }
        }
    }
}

Time Complexity

• Time Complexity: O(N)
  • We visit each node exactly once.
• Space Complexity: O(N)
  • In the worst-case scenario, where the binary tree is completely unbalanced, the recursion could go up to N levels deep, consuming O(N) space on the call stack. In addition, the storage for paths might also be O(N) assuming there are N nodes and thus O(N) number of paths.

By following this approach and code, you should be able to solve the problem of finding all root-to-leaf paths in any binary tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?