Mark As Completed Discussion

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?

Description
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 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?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's our guided, illustrated walk-through.

How do I use this guide?