Good evening! Here's our prompt for today.

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.

1// -9 -> -2 -> 3 -> 5 -> 9
2
3// Linked List Node Definition:
4function Node(val) {
5  this.val = val;
6  this.next = null;
7}

Can you convert it to a binary search tree?

1// Tree Node Definition
2function Node(val) {
3  this.val = val;
4  this.left = null;
5  this.right = null;
6}

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:

1      3
2     / \
3   -2   9
4   /   /
5 -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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

    'PASSED: ' + 'Linked list `4 -> 5 -> 6` is successfully converted to a BST'

var assert = require('assert');

​

function listToBST(head) {

  // fill this in

  return head;

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

​

var tree4 = new Node(5);

Here's our guided, illustrated walk-through.

How do I use this guide?