Only Child

Given a binary tree root, return the number of nodes that are an only child. A node x is an only child if its parent has exactly one child (x).

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Only-Child

Examples

Example 1

Input

• root =

Output

• answer = 2

Explanation

Node 1 is an only child and 3 is an only child.

Example 2

Input

• root =

Output

• answer = 1

Explanation

Node 3 is an only child

Solution