Kth Smallest in BST Editorial

Practice Problem Link: Kth Smallest in BST

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given the root node of a binary search tree and a number k, find out the kth smallest element (1-indexed) in the BST.

Approach

The idea is to traverse the BST in inorder way (increasing) and keep the count of all the nodes visited. When at some point count equals k, then store the value of that node and return it as the answer.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int visitedIndex, value;
void findNode (Node* root, int k) {
	if(root->left != NULL) {
    	findNode(root->left, k);
	}
	visitedIndex++;
	if(visitedIndex == k) {
		value = root->data;
	}
	if(root->right != NULL) {
	    findNode(root->right, k);
	}
}
int findKthSmallest(Node* root, int k) {
	visitedIndex = 0;
	value = INT_MAX;
	findNode(root, k);
	return value;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	int visitedIndex, value;
	void findNode (Node root, int k) {
		if(root.left != null) {
			findNode (root.left, k);
		}
		visitedIndex++;
		if(visitedIndex == k) {
			value = root.data;
		}
		if(root.right != null) {
			findNode(root.right, k);
		}
	}
	int findKthSmallest(Node root, int k) {
	    visitedIndex = 0;
		value = 0;
		findNode(root, k);
		return value;
	}
}