
Asked in ServiceNow
K-th Smallest Element in BST
Your task is to find the ‘K-th’ smallest element in a given Binary Search Tree (BST).
Explanation:
A Binary Search Tree is a binary tree in which for each node, all elements in the left subtree of a node are smaller, and all elements in the right subtree are larger.
Input:
The input begins with an integer ‘T’ representing the number of test cases.
Each test case consists of two parts:
1. An integer ‘K’.
2. A single line containing the elements of the tree in level order format, with node values separated by spaces. '-1' represents a null node.
Output:
For each test case, output the K-th smallest element in the BST. If the K-th smallest element does not exist, return -1.
Example:
Input:
1
3
4 2 7 -1 -1 5 8 -1 -1 -1 -1
Output:
5
Constraints:
- 1 <= T <= 100
- 1 <= N, K <= 3000
- -10^9 <= data <= 10^9
Note:
1. Implement the function to determine the K-th smallest element. No need to print outputs explicitly.
2. Focus is on returning the value of the K-th smallest node, not the node itself.
3. Inputs may include '-1' to denote the absence of a node in certain positions.

AnswerBot
4mo
Find the K-th smallest element in a Binary Search Tree.
Implement a function to find the K-th smallest element in a BST
Traverse the BST in-order and keep track of the count of nodes visited
Return the v...read more
Help your peers!
Add answer anonymously...
Top Software Engineer Interview Questions Asked at ServiceNow
Q. Describe the low-level design of a hashmap.
Q. Given a binary tree, return the level order traversal of its nodes' values. (i.e...read more
Q. Write a recursive function to delete a linked list.
Interview Questions Asked to Software Engineer at Other Companies
Top Skill-Based Questions for ServiceNow Software Engineer
Algorithms Interview Questions and Answers
250 Questions
Data Structures Interview Questions and Answers
250 Questions
Web Development Interview Questions and Answers
250 Questions
Java Interview Questions and Answers
250 Questions
Software Development Interview Questions and Answers
250 Questions
SQL Interview Questions and Answers
250 Questions
Stay ahead in your career. Get AmbitionBox app


Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+
Reviews
10L+
Interviews
4 Cr+
Salaries
1.5 Cr+
Users
Contribute to help millions
AmbitionBox Awards
Get AmbitionBox app

