Correct Binary Tree That Has Two Nodes Swapped - FAANG Interview Question

hey everyone welcome back to my channel

the new video in this video we're

covering another nice uh question of a

binary search tree which is uh you're

given a binary search tree and uh let me

just bring up my iPad here

okay so you are given a binary search

tree let's say you have

five

7

6 this would be let's say

8

3 4 2 1 let's say this is the binary

search tree that is given to you what

the problem is that

uh two nodes in the binary search tree

are swapped it can be any two

nodes it can be any two nod so let's say

this one this one are

swapped

7 and two okay so these two nodes are

swapped now it can be any two nodes we

know that uh how are we going to solve

this one of the ways you can solve this

is you can imagine that let's say if

this is a binary search tree and we do

in ordered reversal then we know that it

will be a sorted array

so if it is a sorted array so in order

reversal before the swapping the sorted

array would look something like this 1 2

3 4

5 6 7 8 this is what it would look like

but what has now happened is 2 and seven

have been

swapped 2 and seven have been swapped so

this question now becomes that okay in a

sorted array Which two elements are

swapped this can be very simple you can

just check the previous one so there

will be two violations one violation is

over here one violation is over

here s is greater than its previous

element two is less than its previous

element okay two

violations so that is what we have to

find these two violations we have to

find in our binary search

tree so what we're do is we're going to

take the first violation is equal to

initially null second violation in equal

equal to null whenever we find the first

violation so the first violation will

arrive when we say that

the current node that you are at so it's

in order reversal is what left current

then right so if I am talking about the

current node it means left is already

been visited so I'm going to be like

let's say I go here then I come here

then I come here here I say if left

node is less than the previous

node it means that first has been found

which is equal to previous node because

this is the previous

one previous

node and then we know that we will find

the first one first because it comes

first so we'll say if first is not equal

to null means first has been

found if first not equal to null first

is equal to previous

node then we will keep on uh going we

will now go over here this looks fine we

will come over

here then we will come over here this

looks fine we'll come over here we'll do

the same condition if this not left it

is the current node

current current node that you are at now

we are at current node if current node

is less than the previous node

yes it is in this

case we will say that the

second node that is wrong is equal to

what previous no previous is six the

current which is the current node

current and that's it after that we will

just swap these two because these are

just pointers to these nodes let

references to these nodes that's it

pretty simple I told you when I was

teaching uh like link list when such

questions are given you don't have to

think you just have to do what the

question is saying and this is what the

question is

saying okay you do understand how I'm

making these previous right so first of

all I will have whenever I choose this

this will be previous then I evaluate

this this will be previous then I

evaluate this I will do this then this

will become previous whenever you keep

evaluating make it previous okay okay if

a current node is evaluated that is

previous then I will go here this will

remain

previous and this will become previous

then I will go here so on and so forth

okay very simple pause this video think

about it and uh by the what is the time

complexity going to be for this solution

we are visiting every node only

once and uh there's the recursive space

also so we are taking o of n

time

right that's what we're

doing and uh for the tree we are only

doing in AIT reversal so it's the height

of the height of the tree okay so here

you can see on the screen uh can by the

way find the link in the description uh

below as well for this code so the

question

was two node swap so we're going to

create two node swap. Java

first of all I'm going to say

class class

node int

value node

left node

right public node in val this dot val is

equal to Val The Constructor is done all

good looking nice

now public Class 2 node

swap here I'm going to create my node

first okay initially that is null node

second and I'm going to create a node

previous that is also initially equal to

null I'm going to say

public

void I'm going to call this one

um

helper okay and I'm going to pass

node let's say for the naming convention

root over here I'm going to call in

order

traversal on the root node while when I

have done in order reversal these two

will be

populated so I will just swap so I will

say

first or I will just

say if I want to swap

it

um yeah let's say ideally I just swap

the let's say just the values are

interchanged okay to make things simpler

but you can swap if the entire nodes are

interchanged as well so I can say first

dot

val first. Val is equal

to

second do

Val second do Val is equal

to Temp so okay initially now we we

assumed that only the values are swapped

so you can

uh you know swap the entire nodes as

well but you are pro experts in that so

you can do it yourself now private

void in ordered reversal node node now I

will just do in ordered

reversal if node is equal to equal to

null

return that's it just

return in order reversal node do

left node do right and in the middle we

will do the work that is what inord

reversal

is so what is the work that we're doing

check if the previous node is violating

the binary search Tre property so

if the previous node do value is

actually greater than the current node

do value also so that we don't get null

pointer

exception if previous node is not equal

to null

and then I will check if first node is

equal to equal to null

in that case I will say that I have

found the first violation this thing

first violation so I will say first is

equal to previous otherwise I will say

second is equal to current which is the

node okay then I will say previous is

equal to current

node that's

it very simple stuff problem

solved

okay very cool

okay that's pretty much about it very

simple solution and we did a trial run

as well you can try running it if you

want uh it's very easy just to create

two trees and uh if you have any

questions let me know in the comment

section below and uh we'll be continuing

the boot camp and introducing newer

Concepts um you know in the next new

year and uh I want to wish you all a

Happy New Year as well and uh yeah see

you next year

bye