Convert Sorted List to Binary Search Tree

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a binary search tree.

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Solution

/**

* @param {ListNode} head

* @return {TreeNode}

const sortedListToBST = head => {

if (!head) {

return null;

}

if (!head.next) {

return new TreeNode(head.val);

}

const node = findMiddle(head);

const middle = node.next;

node.next = null;

const root = new TreeNode(middle.val);

root.left = sortedListToBST(head);

root.right = sortedListToBST(middle.next);

return root;

};

const findMiddle = head => {

let prev = null;

let slow = head;

let fast = head;

while (fast && fast.next) {

prev = slow;

slow = slow.next;

fast = fast.next.next;

}

return prev;

};

Comments