Counting Leaf Nodes

easy

Given a binary tree represented as an array (in level order format), determine the number of leaf nodes present in the tree. A leaf node is a node that has no children. For this problem, if the tree is empty, return 0.

Example 1

Input

[
  [
    1,
    2,
    3,
    null,
    null,
    4,
    5
  ]
]

Output

Explanation. The binary tree is represented as an array in level order. It looks like this: 1 / \ 2 3 / \ 4 5 Leaf nodes are [2, 4, 5], so there are 3 leaf nodes.

Example 2

Input

[
  [
    1,
    2,
    3,
    4,
    null,
    null,
    7
  ]
]

Output

Explanation. The tree can be visualized as: 1 / \ 2 3 / \ 4 7 Leaf nodes are [4, 7] resulting in 2 leaf nodes.

Example 3

Input

[
  [
    1,
    null,
    3
  ]
]

Output

Explanation. The tree configuration appears as: 1 \ 3 Here, the only leaf node is [3].

Example 4

Input

[
  []
]

Output

Explanation. An empty array represents an empty tree. Hence, there are 0 leaf nodes.

Example 5

Input

[
  [
    1
  ]
]

Output

Explanation. The tree comprises only one node, and since it has no children, node [1] is a leaf.

Follow-up: How would you modify your solution if the tree could be a binary search tree or a more general tree where nodes could have more than two children?

Constraints:

The tree array will be non-null but can be empty, indicating an empty tree. Each element in the tree array can either be a positive integer, or `null` representing a missing node.