Teaching Kids Programming – Kth Smallest Element in a BST via Iterative Inorder Traversal Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

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

1 2 3 4 5

3   / \  1   4   \    2

   3
  / \
 1   4
  \
   2

Output: 1

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

1 2 3 4 5 6 7

5       / \      3   6     / \    2   4   /  1

       5
      / \
     3   6
    / \
   2   4
  /
 1

Output: 3

Recursive Inorder Traversal Algorithm for a Binary Search Tree

The Inorder traversal algorithm of a binary search tree gives an ordered sequence. Thus, we can perform Recursive Inorder Traversal and store the elements in a list – and then we can easily retrieve the K-th smallest.

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

# 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:
        def dfs(root):            
            if not root:
                return []
            return dfs(root.left) + [root.val] + dfs(root.right)
        data = dfs(root)
        return data[k - 1]

# 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:
        def dfs(root):            
            if not root:
                return []
            return dfs(root.left) + [root.val] + dfs(root.right)
        data = dfs(root)
        return data[k - 1]

The time and space complexity for above Inorder Traversal algorithm is O(N) as we have to complete visiting all nodes no matter what the value of K is.

Kth Smallest Number in BST via Iterative Inorder Traversal

We actually don’t need to visit all the nodes. We can just visit the first K nodes of the inorder traversal. However, in order to do this, we need a stack to keep all the nodes in the left path. Thus the time complexity is O(H+K) where H is the height and it is about O(N) in the worst case where the tree is degraded into a singly linked list or O(LogN) when the Binary Search Tree is balanced.

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

# 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:
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

# 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:
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

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) —