Sum of Left Leaves

Binary TreeDepth-First SearchRecursionTree

Given the root of a binary tree, calculate the sum of all left leaves in the tree. A leaf is a node with no children. A left leaf is a leaf that is the left child of its parent.

Example 1

Input

[
  [
    3,
    9,
    20,
    null,
    null,
    15,
    7
  ]
]

Output

Explanation. The left leaf of the tree is the node with value 9 and the left leaf of the node 20 is 15. Thus, the sum is 9 + 15 = 24.

Example 2

Input

[
  [
    1
  ]
]

Output

Explanation. The tree only has one node, which is not a leaf.

Example 3

Input

[
  [
    1,
    2
  ]
]

Output

Explanation. The node with value 2 is a left leaf.

Follow-up: Could you solve it both recursively and iteratively?

Constraints:

The tree can have from 1 to 100 nodes. Each node's value will be a non-negative integer.

Views: 3