Convert Binary Tree to Doubly Linked List - FAANG Interview Question

hey everyone welcome back to my channel

in the new video in this video we're

continuing the data algorithms boot camp

and we're doing another nice uh question

of binary trees in this uh the question

says convert a binary tree into a dou

link list so if you don't know what a

dou link list is I would encourage watch

my link list introduction playlist it's

very simple we will have a head and a

tail and you have uh you know we have

have link list like

this

head tail and it will also be pointing

to the previous node so every node is

pointing to the node in front of it and

also behind it okay so that's what a w

link list is and we are given head and

tail

and uh well we are not given head and

tail we have to create it for example

but we are given a binary tree so we're

going to tree like

this

okay this

is five

six this is let's

say three

this is let's say one this is let's say

two no two

four this is let's say

two okay this is

one so you are to convert this tree into

a w link list how are we going to do

this let's say it is a binary search

tree so you have to convert it into a w

link list that is sorted so obviously we

are going to use traversals but the

question is which kind of Tri Ral will

you be using what is the traversal that

gives us the sorted order in a binary

search tree in order traversal so you

start from here will I take this no I

will go in the left I will go in the

left I will go in the left null so I

will then print the current

node which is

one then I will go write nothing then I

will go here bring the current node then

um right then I will go back left is

printed now I'll print the current node

three

then uh

right okay then the left is printed I

will print the current node which is

five and then

write in ordered

reversal we all know what inod reversal

is just watch the link list tutorial

video if you haven't already and if

you're having doubts in this but uh this

is basically how it would work now the

question is very simple we will do in

order reversal but while we are printing

it we will build our dou link list so

when I printed this one I will check is

head equal to null yes currently head is

equal to null because the list is empty

so I will assign this as

head then I will Traverse again now I

have

two so I will be like is head equal to

null no so I will be like the current

pointer that I have let's say tail is

also equal to this I will say tail. next

is equal to this and this currently

previous is equal to the original tail

that I had and then tail will be updated

to the new one then I will print three

we like okay tail do next is equal to

the current node this current node.

previous is equal to the previous

tail okay very easy stuff and until then

we will move forward pause this video

Try it yourself and then uh look at the

code solution okay so I'm going to go to

my folder by the way you can check out

the link link to the code in the

description below going to create a

new Java file or I'm just going to go to

the advanced three questions

one and create a new

file

double link list.

Java zoom in a little

bit

double linked list

cool so that's what we have here what is

the double link list going to have uh it

is going to have as you can see over

here head uh the each node if we talk

about the

node uh what is the node going to have

so let's say I create a new node over

here let's say we

have a new

node uh I'm going to call

it just class node this is going to have

in a value node previous node next

okay public

node Constructor just going to pass

value this. value is equal to Value okay

this is my node uh I'm going to call

this one actually link list

node and I'm going to

create let's say we create a tree node

also trees have what left and right in

val always make sure when you copy paste

tree node left tree node

right public tree

node in

well

Constructor

done

cool sounds good now the W link list

that we have over here I'm going to

create what head and tail so I'm going

to say two

types tree

node head and tree

node

tail sounds

good after this I'm going to

have what am I going to

have

converting how do I create it I have to

convert it from a binary tree it says

binary search tree is given convert into

a w link okay

public it will return three

node

convert

what tree node root by the way this will

not be tree node this will be linkless

node not a tree head and tail tree is

left and right link list head L link

list tail here on the screen you can

see it is saying uh convert tree node

root

sounds good now some basic checks if

root is equal to equal to

null return

null otherwise I'm going to call my

helper function pass my root node in

it okay then I'm going to say return

head sounds

good don't have to make it public I can

say private void

helper helper takes in tree node

node not a

problem okay I can say if node is equal

to equal

to

null return null otherwise in ordered

reversal so what I'm going to do is I'm

going to call the left

first node. left I will call first then

I will

call the current and then in the end

node.

write okay so when I talk about the

current let's say you have found the

answer let's say this is the one so what

do what do we do we create the new node

so link list

node um new node is equal to New Link

list node and the value will be what

node

dot value now if head is equal to to

equal to

null head is equal to new node tail is

also equal to new node only one

element

okay otherwise tail. next is equal to

new

node and then tail itself is equal to

that new node what we just

saw but before that so take next is

equal to new node new node. previous is

equal to tail also is

left new node do previous is equal to

tail is also left and tail is equal to

new

node and then helper node.

right uh that's it

done pretty simple

stuff cool cool this uh code that you

can see I will leave the link in the

description as well you can check it out

all right so that was it pretty short

question but very simple may have looked

intimidating but it was not uh the key

how did I know what to do is uh the hint

I was like you have to do a sending

order that's why we did in ordered

reversal and we did exactly what in Ed

reversal says do the left

first then do the current node whichever

one you're at then do the right simple

stuff if this was unclear you can check

out the previous videos and I'll leave

the links in the description below

thanks a lot for

watching