LC 404 & LC 513

Solution to LeetCode 404 Sum of Left Leaves and LeetCode 513 Find Bottom Left Tree Value.

LeetCode 404

Sum of Left Leaves (Easy) [link]

1] Recursive solution (DFS). Post-order traversal. If the left node is not null and it doesn’t have left and right child, then it is a left leaf. if node != None and node.left == None and node.right == None. We recursively calculate the sum of left node’s left leaf and the right node’s left leaf, and get the sum for the whole tree.

Time complexity O(n). Space complexity O(n).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left_val = self.sumOfLeftLeaves(root.left) # left
        right_val = self.sumOfLeftLeaves(root.right) # right
        
        node_val = 0
        if root.left != None and root.left.left == None and root.left.right == None:
            node_val = root.left.val

        return node_val + left_val + right_val # root

2] Iterative solution (BFS). Pre-order traversal.

Time complexity O(n). Space complexity O(n).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        stack = []
        if not root:
            return stack
        stack.append(root)
        res = 0
        while stack:
            cur = stack.pop()
            if cur.left != None and cur.left.left == None and cur.left.right == None: # root
                res += cur.left.val
            
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)

        return res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        que = deque()
        if not root:
            return que
        que.append(root)
        res = 0
        while que:
            cur = que.popleft()
            if cur.left != None and cur.left.left == None and cur.left.right == None:
                res += cur.left.val

            if cur.left:
                que.append(cur.left)
            if cur.right:
                que.append(cur.right)

        return res

LeetCode 513

Find Bottom Left Tree Value (Medium) [link]

Level-order traversal using Queue. Note that first in first out for Queue. The first node popped out is the leftmost one.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        que = deque([root])
        if not root:
            return None
        res = 0
        while que:
            size = len(que)
            for i in range(size):
                if i == 0:
                    res = que[i].val
                cur = que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
        return res