Teaching Kids Programming – Kth Smallest Element in a BST via Recursive Inorder Traversal 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 BST via Recursive Inorder Traversal Algorithm

The inorder traversal to a Binary Search Tree gives a ordered list. We can perform a Inorder (via Recursion), and then save the list so that we can get the k-th smallest. The time/space complexity is O(N) where N is the number of the nodes in the binary search tree.

# 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)
        return dfs(root)[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)
        return dfs(root)[k-1]

However, if the number of the nodes in the binary search tree is large, and relatively K is small, with above algorithm, we still have to visit all the nodes. A better approach would be to stop visiting the nodes as soon as we have got the K-th smallest node.

# 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:
        ans = None
        
        def dfs(root):
            nonlocal k, ans
            if k < 0:
                return
            if not root:
                return
            dfs(root.left)
            k -= 1
            if k == 0:                
                ans = root.val
                return
            dfs(root.right)
            
        dfs(root)
        return ans

# 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:
        ans = None
        
        def dfs(root):
            nonlocal k, ans
            if k < 0:
                return
            if not root:
                return
            dfs(root.left)
            k -= 1
            if k == 0:                
                ans = root.val
                return
            dfs(root.right)
            
        dfs(root)
        return ans

We can use the iterator to do the inorder traversal. And then we can enumerate and return next one if the index is K-1 (the K-th smallest).

# 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
            yield from dfs(root.left)
            yield root.val
            yield from dfs(root.right)
        return next(c for i, c in enumerate(dfs(root)) if i == 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
            yield from dfs(root.left)
            yield root.val
            yield from dfs(root.right)
        return next(c for i, c in enumerate(dfs(root)) if i == k - 1)

The time complexity is O(H+K) where H is the height of the tree. And space complexity is O(H) for recursion calling stack.

k-th Smallest Element in the Binary Search Tree

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

916 words
Last Post: Teaching Kids Programming - Inorder Traversal Algorithm to Convert Binary Search Tree to Increasing Order Search Tree
Next Post: Teaching Kids Programming - Kth Smallest Element in a BST via Recursive Counting Algorithm

The Permanent URL is: Teaching Kids Programming – Kth Smallest Element in a BST via Recursive Inorder Traversal Algorithm

Algorithms, Blockchain and Cloud

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

Kth Smallest Element in BST via Recursive Inorder Traversal Algorithm

k-th Smallest Element in the Binary Search Tree

Leave a Reply

Kth Smallest Element in BST via Recursive Inorder Traversal Algorithm

k-th Smallest Element in the Binary Search Tree

Related posts:

Leave a Reply