Linked List to Binary Search Tree

Given a sorted linked list node of size n, construct a binary search tree by

• Taking the value of the k = floor(n / 2)(0-indexed) smallest node and setting it as the root.
• Recursively constructing the left subtree using the linked list left of the kth node.
• Recursively constructing the right subtree using the linked list right of the kth node.

Constraints

• n ≤ 100,000

https://binarysearch.com/problems/Linked-List-to-Binary-Search-Tree

Examples

Example 1

Input

• node =

Output

• answer =

Solution