Depth First Search Algorithm (Preorder Traversal) to Compute the Kth Smallest in a Binary Search Tree

Given a binary search tree root, and k return the kth (0-indexed) smallest value in root. It is guaranteed that the tree has at least k + 1 nodes.

For example, with this tree and k = 0 return 2. When k = 2 return 4.

   3
  / \
 2   9
    / \
   7   12
  / \
 4   8

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

Compute the Kth Smallest Number in a Binary Search Tree

We know the Preorder traversal of a binary search tree gives a sorted (ascending) order of the nodes. Therefore, we can perform a DFS (Depth First Search Algorithm) to preorder traversal the binary search tree. We decrement the counter K and once it hits below zero, we remember the node which is the Kth Smallest Number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int solve(Tree* root, int k) {
    Tree* cur;
    function<void(Tree*)> dfs = [&](Tree* root) {
        if (!root) return;
        dfs(root->left);
        k --;        
        if (k == -1) {
            cur = root;
            return;
        }        
        dfs(root->right);
    };
    dfs(root);
    return cur->val;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int solve(Tree* root, int k) {
    Tree* cur;
    function<void(Tree*)> dfs = [&](Tree* root) {
        if (!root) return;
        dfs(root->left);
        k --;        
        if (k == -1) {
            cur = root;
            return;
        }        
        dfs(root->right);
    };
    dfs(root);
    return cur->val;
}

The complexity is O(K) and the space complexity is O(K) due to the usage of stack from Recursion. Another approach would be to preorder traversal the binary search tree and save the nodes in an additional array, then we can just return the Kth element.

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