Kth Smallest in a Binary Search Tree - Amazon Top Interview Questions


Problem Statement :


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.

Constraints

k ≤ n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [3, [2, null, null], [9, [7, [4, null, null], [8, null, null]], [12, null, null]]]

k = 2

Output

4

Example 2

Input

root = [3, [2, null, null], [9, [7, [4, null, null], [8, null, null]], [12, null, null]]]

k = 0

Output

2


Solution :



title-img



                        Solution in C++ :

int ans = 0;

void helper(Tree* root, int& k) {
    if (root) {
        helper(root->left, k);
        if (k == 0) ans = root->val;
        k--;
        helper(root->right, k);
    }
}

int solve(Tree* root, int k) {
    helper(root, k);
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public int solve(Tree root, int k) {
        ArrayList<Integer> al = new ArrayList<>();
        helper(root, al);

        return al.get(k);
    }
    public void helper(Tree node, ArrayList<Integer> al) {
        if (node == null)
            return;
        helper(node.left, al);
        al.add(node.val);
        helper(node.right, al);
    }
}
                    

                        Solution in Python : 
                            
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


def inorder(self):
    if self.left:
        for node in inorder(self.left):
            yield node
    yield self
    if self.right:
        for node in inorder(self.right):
            yield node


setattr(Tree, "inorder", inorder)


class Solution:
    def solve(self, root, k):
        for node in root.inorder():
            if k == 0:
                return node.val
            k -= 1
                    

View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →