Here is the interview question prompt, presented for reference.

We're given a sorted singly linked list (that is, a linked list made of nodes with no pointers to the previous node) where the elements are already arranged in ascending order.

// -9 -> -2 -> 3 -> 5 -> 9

// Linked List Node Definition:
function Node(val) {
  this.val = val;
  this.next = null;
}

Can you convert it to a binary search tree?

// Tree Node Definition
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

Of course, there are many ways to build the BST, so any height balanced BST is acceptable. A height-balanced binary tree is just like it sounds-- the depth of the two subtrees of every node should never differ by more than 1.

Here's one tree that could be formed:

      3
     / \
   -2   9
   /   /
 -9  5

Constraints

• Number of nodes in the linked list <= 100000
• The nodes will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(n)

You can see the full challenge with visuals at this link.