Posted on by Kalkicode
Code Binary Search Tree

Find kth smallest element in BST node js

Find the kth smallest node in binary tree

Js program for Find kth smallest element in BST. Here mentioned other language solution.

// Node JS program for
// K’th smallest element in Binary Search Tree
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
	}
	// Insert a node element
	insert(node, data)
	{
		if (node != null)
		{
			if (node.data >= data)
			{
				// When new element is smaller or equal to current node
				node.left = this.insert(node.left, data);
			}
			else
			{
				// When new element is higher to current node
				node.right = this.insert(node.right, data);
			}
			// Important to manage new node
			return node;
		}
		else
		{
			return new TreeNode(data);
		}
	}
	// Find the kth smallest node in BST
	findKthSmallest(node, k)
	{
		if (node != null)
		{
			// Visit left subtree
			this.findKthSmallest(node.left, k);
			if (this.counter == k)
			{
				// Stop recursion
				return;
			}
			if (this.element == null || this.element.data < node.data)
			{
				// Modified counter variable by one
				this.counter++;
				// Collect possible result
				this.element = node;
			}
			// Visit right subtree
			this.findKthSmallest(node.right, k);
		}
	}
	printKthSsmallest(k)
	{
		if (k <= 0)
		{
			// When given k is not valid positive values
			console.log("Invalid node position " + k);
		}
		else if (this.root == null)
		{
			// When BST are no have elements
			console.log("Empty Binary Search Tree");
		}
		else
		{
			// Reset values
			this.counter = 0;
			this.element = null;
			// Find result
			this.findKthSmallest(this.root, k);
			if (this.counter < k)
			{
				// If In case given kth smallest node are
				// Not exist in binary search tree, then
				console.log("Given " + k + " smallest node are not exist " + this.counter);
			}
			else
			{
				console.log("[" + k + "] smallest node : " + this.element.data);
			}
		}
	}
	// Handle request to add new node
	addNode(key)
	{
		this.root = this.insert(this.root, key);
	}
}

function main()
{
	var tree = new BinarySearchTree();
	/*
	    Make Tree
	    ----------
	        7
	       / \ 
	      /   \
	     4     9
	    / \   / \
	   3   5 8   10
	      /    
	     4     
	*/
	// Add node
	tree.addNode(7);
	tree.addNode(4);
	tree.addNode(3);
	tree.addNode(5);
	tree.addNode(9);
	tree.addNode(8);
	tree.addNode(10);
	tree.addNode(4);
	// Testing
	tree.printKthSsmallest(6);
	tree.printKthSsmallest(4);
	tree.printKthSsmallest(3);
}
// Start program execution
main();

Output

[6] smallest node : 9
[4] smallest node : 7
[3] smallest node : 5

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment