Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Kth Smallest Element in a BST (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a root node of the Binary Search Tree (BST) and integer 'k'. Return the Kth smallest element among all node values of the binary tree.

Examples:

  1. Example 1:
    Input:

        8
   / \
  3   10
 / \    \
1   6    14
   /  \  /
  4   7  13

    k = 4
    Expected Output: 6
    Justification: The in-order traversal of the tree is [1, 3, 4, 6, 7, 8, 10, 13, 14]. The 4th element in this sequence is 6.

  2. Example 2:
    Input:

        5
   / \
  2   6
 /
1

    k = 3
    Expected Output: 5
    Justification: The in-order traversal of the tree is [1, 2, 5, 6]. The 3rd element in this sequence is 5.

  3. Example 3:
    Input:

    1
 \
  3
 /
2

    k = 2
    Expected Output: 2
    Justification: The in-order traversal of the tree is [1, 2, 3]. The 2nd element in this sequence is 2.

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10<sup>4</sup>
  • 0 <= Node.val <= 10<sup>4</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible