Teaching Kids Programming – Kth Smallest Element in a BST via Recursive Counting Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

binary-search-tree

Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints:
The number of nodes in the tree is n.
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
Try to utilize the property of a BST.
Try in-order traversal.
What if you could modify the BST node’s structure?
The optimal runtime complexity is O(height of BST).

Kth Smallest Element in a BST via Recursive Counting Algorithm

Recall that we can count the number of nodes for a given binary tree. And this can be easily done via Depth First Search Algorithm (DFS):

1
2
3
4

def dfs(root):
    if not root:
        return 0
    return dfs(root.left) + 1 + dfs(root.right)

def dfs(root):
    if not root:
        return 0
    return dfs(root.left) + 1 + dfs(root.right)

Or, in one line via lambda function:

1

dfs = lambda x: dfs(x.left) + dfs(x.right) + 1 if x else 0

dfs = lambda x: dfs(x.left) + dfs(x.right) + 1 if x else 0

Another traversal algorithm would be Breadth First Search (BFS) Algorithm and we use a deque (double ended queue):

1
2
3
4
5
6
7
8
9
10
11
12
13

def count(x):
    if not x:
        return 0
    q = deque([x])
    n = 0
    while q:
        a = q.popleft();
        n += 1
        if a.left:
            q.append(a.left)
        if a.right:
            q.append(a.right)
    return n

def count(x):
    if not x:
        return 0
    q = deque([x])
    n = 0
    while q:
        a = q.popleft();
        n += 1
        if a.left:
            q.append(a.left)
        if a.right:
            q.append(a.right)
    return n

Both implementations cost O(N) time and space. With this function, if we know there are exactly k-1 nodes on the left tree of root node, then the root node is the Kth smallest node we are looking for.

If there are more than k-1 nodes on the left tree of the root node, then the k-th smallest node must be in the left tree – which we can recursively solve via (root.left, k).

Otherwise, if there are less than k-1 nodes on the left tree, then the k-thm smallest node should be on the right tree, and we should look for k-1-n node on the right tree aka (root.right, k-n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:        
        count = lambda x: count(x.left) + count(x.right) + 1 if x else 0
 
        leftCount = count(root.left)
        if leftCount == k - 1:
            return root.val
        if leftCount >= k:
            return self.kthSmallest(root.left, k)
        
        return self.kthSmallest(root.right, k - 1 - leftCount)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:        
        count = lambda x: count(x.left) + count(x.right) + 1 if x else 0

        leftCount = count(root.left)
        if leftCount == k - 1:
            return root.val
        if leftCount >= k:
            return self.kthSmallest(root.left, k)
        
        return self.kthSmallest(root.right, k - 1 - leftCount)

The time complexity is O(NK) which is O(N^2) because K is smaller or equal to N. Consider a Increasing Order Search Tree (where the BST does not have left kids), and if we are looking for K=N smallest node (the largest), it would require counting the nodes K times, and each counting is O(N). However, we can optimise the counting by caching.

THe space complexity is O(N) i.e. the stack calling due to Recursion.

k-th Smallest Element in the Binary Search Tree

• Teaching Kids Programming – Kth Smallest Element in a BST via Recursive Inorder Traversal Algorithm
• Teaching Kids Programming – Kth Smallest Element in a BST via Iterative Inorder Traversal Algorithm
• Depth First Search Algorithm (Preorder Traversal) to Compute the Kth Smallest in a Binary Search Tree
• How to Find the Kth Smallest Element in a BST Tree Using Java/C++?
• Teaching Kids Programming – Kth Smallest Element in a BST via Recursive Counting Algorithm

–EOF (The Ultimate Computing & Technology Blog) —