Kth Smallest Element in a BST - Google, Amazon, Facebook Interview Question

hey everyone welcome back to my channel

a new video in this video we're doing

another question um of K smallest

element in a binary search stream medium

there's medium question asked in lot of

companies um let's see where it was

asked K smallest

BST Google Facebook

what Facebook Google and Amazon so it

was asked in like three companies we're

doing the complete algorithms boot camp

so you can check out the links in the

description below and um three questions

usually they are paired up with other

data structures where we did some

questions with like hashmaps um and in

this one we're going to use

um heaps right so this one will be using

Heap and we have done heaps before so a

tree and a heap Tes will be used

together I think you can do it without

Heap as well but don't do it it in the

interview many people comment Kunal you

can do it directly like this why are you

solving it like you know with so many D

success because otherwise if you don't

do that you will get rejected in your

interview this is why I've seen many

compar proms get rejected in the big

tech company interviews um and on

LinkedIn there was a post by a a Fang

recruiter who said that they never hire

like Compu proms because um they don't

know how to communicate well or work

well in teams or whatever um not my

words so what I'm trying to say is when

you're given a question in an interview

and you you know the best answer to that

question don't tell the best answer

right away because they want to learn

about your thought process do the

opposite tell the worst answer the Brute

Force approach first then optimize it

and then try to further optimize it make

it more pretty and clean use less stuff

less lines of code and stuff and you

will be doing very well in your

interview

but let's do this question it says K

smallest element in a binary search tree

I've not done the Heap question videos

yet but if you had watched the video

after I have created it you would know

that whenever it is given to you like

find K smallest or k something you use

heaps the question is solved but since I

have not covered that already um this is

just a little hint that I'm giving you

that

um whenever K smallest something is

given you use heaps but because you're

trying to maintain it right but the

thing is you have to find the smallest

element so what do we do over here uh

this is a binary search tree

so I know that how can I get the sorted

order in ordered reversal we know in

binary search Tre if you do in ordered

reversal you will go sorted order so

three 1 1

4

2 okay if I do in ordered reversal

meaning I start from here then I go left

left nothing then current so one then

right then uh current so 1 2 3 4 see in

ordered

reversals I hope you all know what in

ordered reversal is so I don't have to

explain that so let's say once you have

this in ordered

reversal uh

let's say I talk about this one this

bigger

one okay let me just make this

tree

five 3

6

4 2 1 and K is equal to

3 third smallest

element

in ordered reversal will be

what from

here go here go here go here go here

there's nothing then go back

one

current write nothing current then

write then current then WR 1 2 3 4 5 6

what is the third smallest element third

smallest element is three so that should

be my

answer so what I want you to do is uh

since we are traversing it in uh sorted

order already I know I'm traversing the

tree in sorted order

already I know that I will visit the

tree in the sorted order so whatever the

third element is I can take that or the

kth element is so you can put this in a

heap of size three for example when you

are at one in the Heap you will

put one main Heap for example and then

you take two uh you're going to be like

okay I put two over here then you'll

like I'm at three I put three over

here

right four you can't put four over here

because it's uh like it doesn't

work make

sense right so so even though you

can cuz I don't want to restrict it to a

size so let's say we put in four then

five then six not a problem we put this

in a

heap but what we need to do is okay

there are multiple ways to do it yeah

you can add it all in if you want um so

you can

do just like this 1 2 3 4 five six so

this will be your Heap and then just

remove K elements from the Heap once it

is done so

remove K elements and you know the K

elements that the K element that you

remove it will be your answer one will

be removed two will be removed third

element will be removed this will be the

answer just run a loop from u 1 to K 0

to

K okay multiple ways to do it using Heap

what you can also do is you can only

maintain the

the K smallest

elements

right so only if something is like

smaller than this then only add it in

the

Heap make sense so makebe maybe you can

make a Max Heap in that case the size of

the Heap will be reduced okay so many

ways to do it you can also do it without

the Heap but I would not recommend doing

that as a straight up uh question um in

the interview

so what I would say is that let's say I

create a new

file okay create a new

file and uh what I'm going to do

is here we need a priority Q

so priority Q for

integer minan Heap is equal to

new priority

Q right then I can

say

helper or this will be my in ordered

reversal that I'll be doing and I will

be passing the root the minan Heap and

K right so it will change the mean he

because it'll pass it as a reference

um

private

void

helper TR node

node Min

Heap in

k um now

what if node is equal to equal to

null just return nothing you need to do

we go on the left first because that's

what in ordered reversal is node. left

Min Heap and K

node.

WR mean he and K before that the current

node that's what in order reversal is

left current right for the current what

I will do is I will just add in my M

he no dot

value okay now just take the remove key

elements so how do we do

that something like

that right and I can take an

answer initially is equal to zero I can

say answer is equal to Min he.

offer no not offer the offer is adding

uh min. pole which will remove it and

then in the end

just return the

answer accepted but you can see it's

like not very good in terms of

uh memory and stuff so what I will do is

do this much in the interview and then

uh remove the Heap so the interview like

Heap is taking extra space and stuff can

you remove it what I can do is I can

take

a I can take uh I can

say okay it's smallest

duplicate

okay it's smallest

two don't need

Heap I have a k over

here

so maybe I can take a value over here

private int K and here I can say this do

K is equal to whatever K we

have right provided to us now I will

call my

helper okay but in my helper I don't

need K now and I don't need root now and

uh I will have an answer as well right

so I can say private int

answer and here in the end I will just

return the answer so you can see it's

much more prettier now but in my helper

what will I do

now so instead of maintaining it in a

heap so here you can say instead of

maintaining in a Heap what I can do

is I can

just keep the value track of K so for

example K is equal to 3 when I reach

over here right when I reach over here I

will do K minus 1 so K will be now equal

to 2 and I will check is k equal to Z no

it's not then I will go over here I will

do again K minus 1 so 2 - 1 1 K's value

is one over here let me show you

okay so what I'll do is from when I come

over here I will put it in blue K's

value will be 3 - 1 2 2 is 2 equal to Z

no it's not then I'll go back check this

1 is 1 equal to 0 no it's not go back

minus one 0 is this equal to Z yes

because I have subtracted it K times so

I know that K elements I have seen in

the past so this is my k

element so I will just return from

here

right

so simple recursion I don't need to do

this I will just say k minus minus and

if K becomes

0o result is going to be equal to node

do

Val just return

need now this is much

simpler

right much simpler code less

memory oops this is why when you copy

paste should

always be

careful oh it's answer it's called

answer 100%

okay so much faster and

better go

cool