Binary Tree Paths

• LeetCode: Binary Tree Paths

• Problem:

Given a binary tree, return all root-to-leaf paths.

• Examples:

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

• Analysis:

The feature of a leaf node is that its left and right children are null.

So, inorder traversal to traverse the tree from root to leaf and record all paths.

• Code - Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> results = new ArrayList<String>();
        helper(root, results, "");
        return results;
    }
    private void helper(TreeNode node, List<String> results, String prefix) {
        if (node == null) {
            return;
        }
        if (prefix.length() != 0) {
            prefix += "->";
        }
        prefix += String.valueOf(node.val);
        if (node.left == null && node.right == null) {
            results.add(prefix);
        }
        helper(node.left, results, prefix);
        helper(node.right, results, prefix);
    }
}

• Code - C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> results;
        helper(root, results, "");
        return results;
    }
    void helper(TreeNode* node, vector<string> &results, string prefix) {
        if (node == NULL) {
            return;
        }
        if (prefix.length() != 0) {
            prefix += "->";
        }
        prefix += to_string(node->val);
        if (node->left == NULL && node->right == NULL) {
            results.push_back(prefix);
        }
        helper(node->left, results, prefix);
        helper(node->right, results, prefix);
    }
};

• Code - Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        results = []
        self.helper(root, results, "");
        return results;
    def helper(self, node, results, prefix):
        if node == None:
            return
        if len(prefix) != 0:
            prefix += "->"
        prefix += str(node.val)
        if node.left == None and node.right == None:
            results.append(prefix)
        self.helper(node.left, results, prefix)
        self.helper(node.right, results, prefix)

• Time Complexity: O(N), N is the number of nodes of the tree.

• Space Complexity: O(M), M is the number of the paths from root to leaf.