Binary Tree Path Sum

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

Question

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

Example:

Input:
{1,2,4,2,3}
5
Output: [[1, 2, 2],[1, 4]]
Explanation:
The tree is look like this:
	     1
	    / \
	   2   4
	  / \
	 2   3
For sum = 5 , it is obviously 1 + 2 + 2 = 1 + 4 = 5


Input:
{1,2,4,2,3}
3
Output: []
Explanation:
The tree is look like this:
	     1
	    / \
	   2   4
	  / \
	 2   3
Notice we need to find all paths from root node to leaf nodes.
1 + 2 + 2 = 5, 1 + 2 + 3 = 6, 1 + 4 = 5 
There is no one satisfying it.

Analyzation

Recursion

In this problem, it needs three parameters: root, path, result.

Therefore, create a helper function with the above parameters and continue building the path if there is left node and/or right node till it is a leaf node.

The Code

class Solution:
    """
    @param: root: the root of binary tree
    @param: target: An integer
    @return: all valid paths
    """
    def binaryTreePathSum(self, root, target):
        # write your code here
        if root is None:
            return []
            
        result = []
        self.dfs(root, target, [root.val], result)
        
        return result
    
    def dfs(self, root, target, path, result):
        # if leaf node:
        if root.left is None and root.right is None:
            if sum(path) == target:
                result.append(path[:])
                return
        
        # if not leaf node
        if root.left:
            self.dfs(root.left, target, path + [root.left.val], result)
        
        if root.right:
            self.dfs(root.right, target, path + [root.right.val], result)

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).