Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Kth smallest node in BST

Moderate
0/80
Average time to solve is 15m
50 upvotes
Asked in companies
WalmartMakeMyTripAmazon

Problem statement

You have been given a Binary Search Tree of integers. You are supposed to return the k-th (1-indexed) smallest element in the tree.


For example:
For the given binary search tree and k = 3

Example

The 3rd smallest node is highlighted in yellow colour.   
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
3
10 5 15 4 7 14 16 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
7
Explanation of Sample Input 1:

Example

The third-smallest node is 7.
Sample Input 2:
2
-2 -4 1 -5 -1 -1 -1 -1 -1
Sample Output 2:
-4
Explanation of Sample Input 2:
The second-smallest node is -4.
Constraints:
1 <= N <= 10000
1 <= K <= N
-10^8 <= data <= 10^8 and data != -1

Where ‘N’ is the total number of nodes in the binary search tree, ‘K’ is the given integer and “data” is the value of the binary search tree node.

Time Limit: 1sec
Full screen
Console