Linked List to ZigZag Tree Path

Given a singly linked list node, convert it to a binary tree path using these rules:

• The head of the linked list is the root.
• Each subsequent node is the left child of the parent if its value is smaller, otherwise it’s the right child.

Constraints

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

https://binarysearch.com/problems/Linked-List-to-ZigZag-Tree-Path

Examples

Example 1

Input

• node =

Output

• answer =

Example 2

Input

• node =

Output

• answer =

Solution