JSFiddle - React, Tailwind, and code Playground

by asdf

HTML

<!-- BST (Binary Search Tree) is a tree where node has some value (number) and all nodes in left subtree are less than node value. All nodes in right subtree are equal or bigger than node value. For this task nodes can contain other information if you want. Your task is to find k-th smallest element in BST. 
For example, https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/2000px-Binary_search_tree.svg.png
continue example for BST above: if k=3 then the answer will be 4, for k=8 answer is 13-->

JavaScript

// find k-th smallest element in BST
function getNode(value, left, right) {
   return {
   		 value: value,
       left: left,
       right: right
   };
}

var node1 = getNode(1);
var node4 = getNode(4);
var node7 = getNode(7);
var node6 = getNode(6, node4, node7);
var node3 = getNode(3, node1, node6);
var node13 = getNode(13);
var node14 = getNode(14, node13);
var node10 = getNode(10, undefined, node14);
var root = getNode(8, node3, node10);

function processTree(node) {
	var count = 1;
  if (node.left) {
		processTree(node.left);
    count += node.left.nodesCount;
  }
  if (node.right) {
		processTree(node.right);
    count += node.right.nodesCount;
  }
  node.nodesCount = count;
}
function getKthSmallest(k, node) {
  var temp, val, index;
  if (node.nodesCount < k) {
  	return;
  }
  index = 1 + (node.left ? node.left.nodesCount : 0);
  if (index === k) {
  	return node.value;
  }
  if (index > k) {
  	val = getKthSmallest(k, node.left);
  } else {
  	val = getKthSmallest(k-index, node.right);
  }
  return val;
}
// in order traversal algorithm
function inOrderTraversal(k, node, arr) {
  var res;
  if (arr.length === k) {
    return arr[k-1];
  }
  if (!node) {
  	return;
  }
  res = inOrderTraversal(k, node.left, arr);
  arr.push(node.value);
  res = res || inOrderTraversal(k, node.right, arr);
  return res;
}
processTree(root);
console.log(getKthSmallest(3, root));
console.log(getKthSmallest(8, root));
console.log(getKthSmallest(10, root));
console.log(getKthSmallest(1, root));
console.log(getKthSmallest(7, root));
console.log('=========================');
console.log(inOrderTraversal(3, root, []));
console.log(inOrderTraversal(8, root, []));
console.log(inOrderTraversal(10, root, []));
console.log(inOrderTraversal(1, root, []));
console.log(inOrderTraversal(7, root, []));