Temp data structures and algorithms tutorial solu bstinsert root

Topics
covered
in
this
session

Ques=on
1

•Traverse

the

following

binary

tree:

(a)

in
preorder;

(b)

in

inorder;

(c)

in
postorder.
Show the
contents
of
the
traversal
as
the
algorithm progresses.

Solu=on
i.Preorder:

a
b
d
e
c
f


(root-­‐leG-­‐right)

•
(Understanding
the
execu=on
of
a
recursive
algorithm.)
For
the
binary
search tree
below,
trace
step
by
step
the
execu=on
of
the
algorithm
BSTinsert_recurs(
).

BSTinsert_recurs
(root,
temp)
{





if
(temp.data
≤
root.data)
{











if
(root.leG
=
=
null)
















root.leG
=
temp











else
















BSTinsert_recurs
(root.leG,
temp);












}






else
{

//
goes
to
right











if
(root.right
=
=
null)
















root.right
=
temp











else
















BSTinsert_recurs
(root.right,
temp);






}
}

if
(root.right
=
=
null)
















root.right
=
temp
else
















BSTinsert_recurs
(root.right,
temp);

}
}

Solu=on
(3)

Solu=on
(4)

Return
to
Finish

17

The
following
algorithm
seeks
to
compute
the
number
of
leaves
in
a
binary
tree.

Is
this
algorithm
correct?
If
it
is,
prove
it;
if
it
is
not,
make
an
appropriate
correc=on.

Solu=on

The
algorithm
doesn't
work
correctly
on
the
one-­‐node
binary tree:
it
returns
0
instead
of
1.
Here
is
a
corrected
version:

Ques=on
4

•
(Understanding
the
design
of
a
recursive
algorithm.)
The binary
tree
is
recursive
in
nature.
The
tree
traversal
algorithms that
we
discussed
in
the
lecture
exemplify
the
basic
fact
that we
are
led
to
consider
recursive
algorithms
for
binary
tree.

The
algorithm
for
calcula=ng
height
of
a
tree
is
as
follows:

Algorithm
height
(T)
{

if
(
T
=
=
null
)
return
-­‐1;

//
empty
tree

if
(T.leG
==
null
and
T.right
==
null)
return
0;
//
one
node
tree
lh
=
height(T.leG);

rh
=
height
(T.right);