1class Node {
2  constructor(value) {
3    this.value = value;
4    this.next = null;
5    this.bottom = null;
6  }
7}
8
9function newNode(value) {
10  return new Node(value);
11}
12
13function constructLinkedList() {
14  let head = newNode(5);
15  head.bottom = newNode(7);
16  head.bottom.bottom = newNode(8);
17  head.bottom.bottom.bottom = newNode(30);
18
19  head.next = newNode(10);
20  head.next.bottom = newNode(20);
21
22  head.next.next = newNode(19);
23  head.next.next.bottom = newNode(22);
24  head.next.next.bottom.bottom = newNode(50);
25
26  head.next.next.next = newNode(28);
27  head.next.next.next.bottom = newNode(35);
28  head.next.next.next.bottom.bottom = newNode(40);
29  head.next.next.next.bottom.bottom.bottom = newNode(45);
30
31  return head;
32}
33
34const head = constructLinkedList();
35
36function printList(head) {
37  let element = [];
38  let current = head;
39  while (current != null) {
40    element.push(current.value);
41    let bottom = current.bottom;
42    while (bottom != null) {
43      element.push(bottom.value);
44      bottom = bottom.bottom;
45    }
46    current = current.next;
47  }
48  return element;
49}
50
51class BSTNode {
52  constructor(val) {
53    this.data = val;
54    this.left = null;
55    this.right = null;
56  }
57}
58class BST {
59  constructor() {
60    this.root = null;
61  }
62  insert(val) {
63    const newNode = new BSTNode(val);
64    if (!this.root) {
65      this.root = newNode;
66      return;
67    }
68    let current = this.root;
69    while (current) {
70      if (val < current.data) {
71        if (!current.left) {
72          current.left = newNode;
73          return;
74        }
75        current = current.left;
76      } else if (val > current.data) {
77        if (!current.right) {
78          current.right = newNode;
79          return;
80        }
81        current = current.right;
82      } else {
83        return;
84      }
85    }
86  }
87  printInOrder(node = this.root) {
88    if (!node) return [];
89    return [...this.printInOrder(node.left), node.data, ...this.printInOrder(node.right)];
90  }
91}
92function createBSTFromList(head) {
93  let bst = new BST();
94  let arr = printList(head);
95  for (let i = 0; i < arr.length; i++) {
96    bst.insert(arr[i]);
97  }
98  let arrSorted = bst.printInOrder();
99
100  return arrSorted;
101}
102
103function createLinkedListFromArray(arr) {
104  if (arr.length === 0) {
105    return null;
106  }
107  let head = newNode(arr[0]);
108  let current = head;
109  for (let i = 1; i < arr.length; i++) {
110    current.bottom = newNode(arr[i]);
111    current = current.bottom;
112  }
113
114  return head;
115}
116
117console.log(printList(createLinkedListFromArray(createBSTFromList(head))));
118//TC - worst case O(N*N) ideal case O(NlogN)
119