Good morning! 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.
JAVASCRIPT
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
?

JAVASCRIPT
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:
SNIPPET
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
and1000000000
- 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
67
'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);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's how we would solve this problem...
How do I use this guide?