Trees
Exercise 9
Given a T compute the height of T
binary
Solution
T height of empty tree is 0
ha It max he ha
ELITE
information bottom
flow up
b4
88
height x
if x NIL return O
he height x left
8 800
t
ha height x right
return It max he ha
Exercise 2
free T compute the subtree site
Given a
of every node
Example
30 5
old
Solution
at set on
base case sa o
y 9
Subtree x
n Oto to s
if NIL return o
se subtree x left
she Subtree x
right
return set on to
6
O
88 Oo o
o o
Exercise 3
Given a tree print keys of every node at given
level K
level
O
I
8,6 2
I 3
4
Information goes Top down
Print Levelk level
x I
if X NIL return
PrintLevelk x left K level s
PrintLevelk x right K level s
if level K print k Key
First call
level o
Print Levelk root 2 o
level output 3 717 20
wife É s
what about
level as es
different visits for
level4 beretal this Problem
If T is a BST print inorder
Print Level K X K Just 2 parameters
if x NIL return
PrintLevel K x left K T
Print Level K e right K l
if K 0 print x key
Exercise a
Given a free T print the key of every node x
such that x
key equals the subtree site of X
Solution
PK
if X NIC return o
se f x left
sr
f x
right
sx set st to
if ox X key print x key
return sx
Exercise le bis
if T is BST
a print keys of node
x subtree x X key sorted
Too hard without storing subtree sites for
every node
Very slow and thus bad solution
PK
if X NIC return o
se l ix eat
Sh Subtree site x Light
if
return
iii
ox X
st
key print x key
8
r
f
ifi
o
i
Exercise 5
Given a tree T print the key of every node x
such that the sum
of keys on the root to x
path equals x's subtree site
Example
rotto x path
tests
Ig
A
Solution
VERY BAD SOLUTION
Path Sum x sum Subtree site x
N NK return O
if if x
sun sum x key see Subtreesite eldt
path sum x left sum she Subtree site aright
pathSum x Light sum return retort
if sum Subtreesise x usum o
sumo
print x key
1 um 3
VERY BAD n time
1111111
PathSum x sum
PathSumn x sum
if x Nic return
NIL return sun sum x key
if X O
pathsum x left sum
sum sum t X Key pathSum x right sum
se PathSum x left sum if sum subtreesise x
print x key
Sh PathSum G right Dum
Dx Slt or A Subtree site x
if x NK return 0
If sum DX
see Subtreesiteeldt
print C key su Subtreesitenight
return set onto
return DX
Complexity O n time
Exercise 6
Given free T check T BST
a
if is a
Wrong Solution
U Key IX key and A key I v key
68
Exercise t before doing 6
Check if T satisfies property
prop x
if x NK return True
be prop x left
bra prop A right
if X left Nic and A left key Akey
return False
if X right f Nic and A right Key IX key
return False
return be and br
Now Exercise 6
VERY BAD SOLUTION Complexity Ofa
time
Check BST x
if x NIL return True
bl check BST x left
b r checkBST x right
Ml martree x let
mr min tree x night
if me x key on mu e x key
return False
return be and be
max tree x
if x NIL return 8
Me man tree x left
Mr max tree x right
return max x key Me Mr
minimax tree x
if x NIL return w
me Me mmmm tree x left
ma Mr I'imaxtree x right
return minkkeyme mr max x key Ml Mr
