How should I practice Kth Smallest Element in a Binary Search Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Salesforce onsite interview problems in FastPrep.

Is Kth Smallest Element in a Binary Search Tree associated with Salesforce?

FastPrep tags this as a Salesforce onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Kth Smallest Element in a Binary Search Tree

Learn this problem

● Medium

SalesforceFULLTIMEONSITE INTERVIEW

See Salesforce hiring insights

Problem statement

Insert the values in insertionOrder into an initially empty binary search tree in the given order. Then return the kth-smallest key, where k is one-indexed.

Use an iterative inorder traversal and stop as soon as the kth node is visited.

Function

kthSmallest(insertionOrder: int[], k: int) → int

Examples

Example 1

insertionOrder = [5,3,6,2,4,1]k = 3return = 3

The inorder sequence is [1,2,3,4,5,6], whose third value is 3.

Example 2

insertionOrder = [2,1,3]k = 1return = 1

The first node visited by inorder traversal has key 1.

Constraints

1 <= insertionOrder.length <= 100000.
All values in insertionOrder are distinct signed 32-bit integers.
1 <= k <= insertionOrder.length.