404.sum-of-left-leaves.md

404. Sum of Left Leaves

Test Cases

Normal Cases

Input: 
        1
      /   \
     3     5
         /   \
        4     7
Output: 3 + 4

Edge / Corner Cases

Input: 1
Output: 0

Input: 
    1
  /   
 2
Output: 2

Input:
    1 
      \
       2
Output: 0

Input:
        1
      /   \
     2     4
    /     / 
   3     6
Output: 3 + 6

    1
  /   \
 3     4
      / 
     6
      \ 
       9
Output: 3, but 6 and 9 are not left leaf node.

Input:
    1
  /   \
 3     4
   \
    5
   /
  9
Output: 9, but 3 is not left leaf node.

DFS

// With a global variable
private var sum = 0
fun sumOfLeftLeaves(root: TreeNode?): Int {
    dfs(root, null)
    return sum
}

private fun dfs(root: TreeNode?, parent: TreeNode?) {
    if (root == null) return
    if (root.left == null && root.right == null && parent?.left == root) {
        sum += root.`val`
        return
    }
    dfs(root.left, root)
    dfs(root.right, root)
}

// -----------------------------------------------
// Or equivalently, dfs() function returns the sum
fun sumOfLeftLeaves(root: TreeNode?): Int {
    return dfs(root, null)
}

private fun dfs(root: TreeNode?, parent: TreeNode?): Int {
    if (root == null) return 0
    if (root.left == null && root.right == null && parent?.left == root) {
        return root.`val`
    }
    return dfs(root.left, root) + dfs(root.right, root)
}

• Time Complexity: O(n)
• Space Complexity: O(n)

BFS

We can use the same idea above to solve this problem by BFS, we enqueue node with isLeft state and check if the current node is a left leaf node.

 fun sumOfLeftLeaves(root: TreeNode?): Int {
    if (root == null) return 0
    var sum = 0
    // It's ok to use Stack
    val queue = ArrayDeque<Pair<TreeNode, Boolean>>() 
    queue.addLast(root to false)
    while (queue.isNotEmpty()) {
        val (node, isLeft) = queue.removeFirst()
        if (node.left == null && node.right == null && isLeft) {
            sum += node.`val`
        }
        if (node.left != null) {
            queue.addLast(node.left to true)
        }
        if (node.right != null) {
            queue.addLast(node.right to false)
        }
    }
    return sum
}

Or we don't enqueue node with isLeft state, we check if left child of every node is a left leaf node and sum it.

fun sumOfLeftLeaves(root: TreeNode?): Int {
    if (root == null) return 0
    var sum = 0
    // It's ok to use Stack
    val queue = ArrayDeque<TreeNode>() 
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        if (node.left != null) {
            if (node.left.isLeaf()) {
                sum += node.left.`val`
            } else {
                queue.addLast(node.left)
            }
        }
        if (node.right != null) {
            queue.addLast(node.right)
        }
    }
    return sum
}

private fun TreeNode.isLeaf(): Boolean {
    return this.left == null && this.right == null
}