257. Binary Tree Paths

Description

Given a binary tree, the task is to return all root-to-leaf paths as a list of strings. Each path should be formatted as a string where nodes are joined by "->".

Intuition

The problem can be approached by recursively traversing the tree. As we move from the root to the leaves, we can build a path string and add it to the result once we reach a leaf node. The key insight is that each leaf node represents the end of a unique path from the root.

Approach

1. Recursive Traversal: - Start from the root and traverse the tree. For each node, append its value to the current path. - If a node is a leaf (i.e., it has no left or right child), add the current path to the result list. - If the node is not a leaf, recursively traverse its left and right children, passing the current path down to them.
2. Path Construction: - The path is constructed as a string, where each node value is appended with "->" if it’s not the end of the path. - When a leaf node is encountered, the path string is complete and is added to the result list.
3. Edge Cases: - If the tree is empty (i.e., the root is null), the result should be an empty list.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the tree. We visit each node exactly once during the traversal.

Space Complexity:

O(H), where H is the height of the tree. This is the maximum depth of the recursion stack. In the worst case, the space complexity could be O(N) if the tree is skewed (i.e., all nodes are on one side).

Code

C++

class Solution {
public:
    vector binaryTreePaths(TreeNode* root) {
        vector res;
        if (!root) return res;

        function path = [&](string p, TreeNode* node) {
            if (node && !node->left && !node->right) {
                string pathV = p.empty() ? to_string(node->val) : p + "->" + to_string(node->val);
                res.push_back(pathV);
                return;
            } else if (node) {
                string pathV = p.empty() ? to_string(node->val) : p + "->" + to_string(node->val);
                if (node->left) {
                    path(pathV, node->left);
                }
                if (node->right) {
                    path(pathV, node->right);
                }
            }
        };

        path("", root);
        return res;
    }
};

Python

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        res = []
        if not root:
            return res

        def path(p: str, node: TreeNode):
            if node and not node.left and not node.right:
                pathV = f"{p}->{node.val}" if p else str(node.val)
                res.append(pathV)
            elif node:
                pathV = f"{p}->{node.val}" if p else str(node.val)
                if node.left:
                    path(pathV, node.left)
                if node.right:
                    path(pathV, node.right)

        path("", root)
        return res

Java

class Solution {
    public List binaryTreePaths(TreeNode root) {
        List res = new ArrayList<>();
        if (root == null) return res;

        path("", root, res);
        return res;
    }

    private void path(String p, TreeNode node, List res) {
        if (node != null && node.left == null && node.right == null) {
            String pathV = p.isEmpty() ? String.valueOf(node.val) : p + "->" + node.val;
            res.add(pathV);
        } else if (node != null) {
            String pathV = p.isEmpty() ? String.valueOf(node.val) : p + "->" + node.val;
            if (node.left != null) {
                path(pathV, node.left, res);
            }
            if (node.right != null) {
                path(pathV, node.right, res);
            }
        }
    }
}

JavaScript

var binaryTreePaths = function (root) {

    let res = [];
    let path = function (p, node) {

        if (node && !node.left && !node.right) {
            let pathV = p ? p + "->" + node.val : String(node.val);
            res.push(pathV);
            return;

        } else if (node) {
            let pathV = p ? p + "->" + node.val : String(node.val);
            if (node.left) {
                path(pathV, node.left)
            }
            if (node.right) {
                path(pathV, node.right)
            }
        } else {
            
            return;
        }
    }
    path("", root);
    return res;

};