Vertical Lines in Binary Tree

Given a binary tree root, return the number of unique vertical lines that can be drawn such that every node has a line intersecting it. Each left child is angled at 45 degrees to its left, while the right child is angled at 45 degrees to the right.

For example, root and root.left.right are on the same vertical line.

Constraints

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

https://binarysearch.com/problems/Vertical-Lines-in-Binary-Tree

Examples

Example 1

Input

• root =

Output

• answer = 4

Example 2

Input

• root =

Output

• answer = 5

Explanation

There’s a unique vertical line over every node.

Solution