Kth Largest Element in a BST
Wed Apr 03 2024 Kth Largest Element Retrieval:
A method tailored to identify the kth largest element by leveraging the BST's inherent in-order traversal property, which naturally produces a sorted sequence of its elements. By first generating this sorted array, the task then simplifies to accessing the element at the appropriate index from the end, effectively pinpointing the kth largest value.
1class Node {
2 constructor(data) {
3 this.data = data;
4 this.right = null;
5 this.left = null;
6 }
7}
8
9class BST {
10 constructor() {
11 this.root = null;
12 }
13 insert(val) {
14 const newNode = new Node(val);
15 if (!this.root) {
16 this.root = newNode;
17 return;
18 }
19 let current = this.root;
20 while (current) {
21 if (val < current.data) {
22 if (!current.left) {
23 current.left = newNode;
24 return;
25 }
26 current = current.left;
27 } else if (val > current.data) {
28 if (!current.right) {
29 current.right = newNode;
30 return;
31 }
32 current = current.right;
33 } else {
34 return;
35 }
36 }
37 }
38 printInOrder(node = this.root) {
39 if (!node) return [];
40 return [...this.printInOrder(node.left), node.data, ...this.printInOrder(node.right)];
41 }
42 printKthLargest(node = this.root, k) {
43 if (!node) return [];
44 let arr = this.printInOrder(node);
45 return arr[arr.length - k];
46 }
47}
48
49const tree = new BST();
50tree.insert(5);
51tree.insert(3);
52tree.insert(7);
53tree.insert(2);
54tree.insert(4);
55tree.insert(6);
56tree.insert(8);
57//console.log(tree.printInOrder())
58console.log(tree.printKthLargest(tree.root, 2));
59