How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find Kth Smallest in BST | Uber Coding Question

Q: Find Kth Smallest in BST

This question evaluates understanding of binary search tree properties, ordered data retrieval, and algorithmic efficiency in locating the k-th smallest element.

Find Kth Smallest in BST

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given the root of a binary search tree and an integer `k`. Return the value of the node that would appear in the `k`th position if all node values were listed in ascending order. A binary search tree has the property that for every node: - all values in the left subtree are smaller than the node value, and - all values in the right subtree are larger than the node value. You may assume `1 <= k <= number of nodes in the tree`. Example: - Input: root = [5,3,6,2,4,null,null,1], k = 3 - In-order traversal gives: [1,2,3,4,5,6] - Output: 3 Discuss an efficient approach and analyze its time and space complexity.

Quick Answer: This question evaluates understanding of binary search tree properties, ordered data retrieval, and algorithmic efficiency in locating the k-th smallest element.

You are given the root of a binary search tree (BST) and an integer k. Return the value of the node that would appear in the kth position if all node values were listed in ascending order. A BST has the property that every value in a node's left subtree is smaller than the node's value, and every value in a node's right subtree is larger than the node's value. For this problem, the tree is provided as a level-order list where None represents a missing child.

Constraints

1 <= number of nodes in the tree <= 10000
1 <= k <= number of nodes in the tree
All node values are unique integers
-100000 <= node value <= 100000
The input tree satisfies the binary search tree property

Examples

Input: ([5, 3, 6, 2, 4, None, None, 1], 3)

Expected Output: 3

Explanation: The in-order traversal is [1, 2, 3, 4, 5, 6], so the 3rd smallest value is 3.

Input: ([10], 1)

Expected Output: 10

Explanation: There is only one node, so the 1st smallest value is 10.

Input: ([8, 3, 10, 1, 6, None, 14, None, None, 4, 7, 13], 1)

Expected Output: 1

Explanation: The smallest value in the BST is 1, so k = 1 returns 1.

Input: ([4, 2, 6, 1, 3, 5, 7], 5)

Expected Output: 5

Explanation: The in-order traversal is [1, 2, 3, 4, 5, 6, 7], so the 5th smallest value is 5.

Input: ([0, -3, 9, -10, -1, 5], 4)

Expected Output: 0

Explanation: The in-order traversal is [-10, -3, -1, 0, 5, 9], so the 4th smallest value is 0.

Input: ([1, None, 2, None, 3, None, 4], 4)

Expected Output: 4

Explanation: This right-skewed BST has ascending order [1, 2, 3, 4], so the 4th smallest value is 4.

Hints

What traversal of a BST visits values in ascending order?
You do not need to store every value; count nodes as you visit them and stop when you reach k.

Quick Overview

This question evaluates understanding of binary search tree properties, ordered data retrieval, and algorithmic efficiency in locating the k-th smallest element.