[JavaScript] Binary search tree find kth largest value

find-kth-largest.js

const assert = require("assert");

function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

function findKthLargestValueInBst(tree, k) {
  const result = [];
  traverseInorder(tree, result);
  return result[result.length - k]?.value || -1;
}

function traverseInorder(tree, result) {
  if (tree === null) return;
  tree.left && traverseInorder(tree.left, result);
  result.push(tree);
  tree.right && traverseInorder(tree.right, result);
}

/*
  tree = 15
       /   \
      5     20
     / \   / \
    2  5  17 22
   / \
  1  3
   k = 3,
   returns 17
*/

const tree = new BST(15);
tree.left = new BST(5);
tree.left.right = new BST(5);
tree.left.left = new BST(2);
tree.left.left.left = new BST(1);
tree.left.left.right = new BST(3);
tree.right = new BST(20);
tree.right.left = new BST(17);
tree.right.right = new BST(22);

const k = 3;
const expected = 17;

assert.deepStrictEqual(findKthLargestValueInBst(tree, k), expected);

optimized.js

const assert = require("assert");

function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

// O(h + k) time | O(h) space - where h is the height of tree, and k is the input paremeter
function findKthLargestValueInBst(tree, k) {
  const treeInfo = {
    numberOfVisitedNode: 0,
    lastVisitedValue: -1
  };
  reverseInorderTraverse(tree, k, treeInfo);
  return treeInfo.lastVisitedValue;
}

function reverseInorderTraverse(node, k, treeInfo) {
  if (node === null || treeInfo.numberOfVisitedNode >= k) return;
  // Right, root, left
  reverseInorderTraverse(node.right, k, treeInfo);
  if (treeInfo.numberOfVisitedNode < k) {
    treeInfo.numberOfVisitedNode++;
    treeInfo.lastVisitedValue = node.value;
    reverseInorderTraverse(node.left, k, treeInfo);
  }
}


/*
  tree = 15
       /   \
      5     20
     / \   / \
    2  5  17 22
   / \
  1  3
   k = 3,
   returns 17
*/

const tree = new BST(15);
tree.left = new BST(5);
tree.left.right = new BST(5);
tree.left.left = new BST(2);
tree.left.left.left = new BST(1);
tree.left.left.right = new BST(3);
tree.right = new BST(20);
tree.right.left = new BST(17);
tree.right.right = new BST(22);

const k = 3;
const expected = 17;

assert.deepStrictEqual(findKthLargestValueInBst(tree, k), expected)