Sum of Left Leaves

Binary TreeDepth-First SearchRecursionTree

Given the root of a binary tree, return the sum of all left leaves in the tree. A node is considered a left leaf if it is the left child of its parent and it has no children of its own.

Example 1

Input

[
  {
    "val": 3,
    "left": {
      "val": 9,
      "left": null,
      "right": null
    },
    "right": {
      "val": 20,
      "left": {
        "val": 15,
        "left": null,
        "right": null
      },
      "right": {
        "val": 7,
        "left": null,
        "right": null
      }
    }
  }
]

Output

Explanation. In the given tree, 9 and 15 are the left leaves. Therefore, their sum is 9 + 15 = 24.

Example 2

Input

[
  {
    "val": 1,
    "left": {
      "val": 2,
      "left": null,
      "right": null
    },
    "right": null
  }
]

Output

Explanation. The left leaf is 2, hence the sum is 2.

Example 3

Input

[
  {
    "val": 5,
    "left": null,
    "right": {
      "val": 8,
      "left": null,
      "right": null
    }
  }
]

Output

Explanation. There are no left leaves in the tree.

Follow-up: Can you solve the problem recursively and iteratively?

Constraints:

The number of nodes in the tree will be in the range [1,1000]. -100 <= Node value <= 100

Views: 3