Binary Tree Paths

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

Question

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

Example:

Input：{1,2,3,#,5}
Output：["1->2->5","1->3"]
Explanation：
   1
 /   \
2     3
 \
  5


Input：{1,2}
Output：["1->2"]
Explanation：
   1
 /   
2    

Analyzation

Recursion

Firstly, put the root node to the path if it exists.

Secondly, if the left and right subtrees don’t exist, simply add the path to the final answer list because this path is constructed.

Thirdly, if the current node has subnode(s), recursively call the function itself based on the left and right subtree.

The Code

class Solution:
    """
    @param root: the root of the binary tree
    @return: all root-to-leaf paths
    """
    def binaryTreePaths(self, root):
        # The most intuitive method is to use depth-first search. When depth-first search traverses a binary tree, we need to consider the current node and its child nodes.
        # If the current node is not a leaf node, add the node at the end of the current path, and continue to recursively traverse each child node of the node.
        # If the current node is a leaf node, then after adding the node at the end of the current path, we will get a path from the root node to the leaf node. Just add this path to the answer.
        # In this way, after traversing the entire binary tree, we get all the paths from the root node to the leaf nodes. Of course, the depth-first search can also be implemented in a non-recursive manner, so I won’t repeat it here.
        
        def construct_path(root, path):
            if root:
                path += str(root.val)
                if root.left is None and root.right is None:
                    ans.append(path)
                else:
                    path += '->'
                    construct_path(root.left, path)
                    construct_path(root.right, path)
                
        ans = []
        construct_path(root, '')
            
        return ans

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).