Binary
Sea
rch
T
rees
ResetProgress
RevealSolutions
1Definitions
Supposethat
the
nodes
A,B
,
C
ina
bina
ry
sea
rch
tree
a
re
a
rranged
as
follo
ws.
A
B
C
Whichof
the
follo
wing
describes
the
relationship
bet
w
een
A,B
,
C
?
A
≤
B,
C
A
≥
B,
C
A
≤
B
≤
C
B
≤
A
≤
C
Correct
A
B
C
Whatis
the
relationship
bet
w
een
A,B
,
C
?
B
≤
A
≤
C
B
≤
C
≤
A
C
≤
B
≤
A
C
≤
A
≤
B
Correct
Theirp
re-o
rder
traversals.
Theirin-o
rder
traversals.
Theirpost-o
rder
traversals.
Theirroot
nodes.
Correct
O
(log
n
)
Ω(log
n
)
Θ(log
n
)
Allof
the
above.
Correct
2
1
3
Yes
No
Correct
1
2
3
Yes
No
Correct
4
2
1
3
5
Yes
No
Correct
O
(log
n
)
Ω(log
n
)
Θ(log
n
)
Allof
the
above.
Correct
45
180
30
Allof
the
above.
Correct
i
≥
Ω(
n
)
i
≥
Ω(
√
n
)
i
≤
0
.
99
n
Correct
Θ(
n
)
Θ(
√
n
)
Θ(log
n
)
Correct
Now
suppose
that
nodes
A,B
,
C
are
a
rranged
as
follo
ws
in
the
bina
ry
sea
rch
tree.
Ift
w
o
different
bina
ry
sea
rch
trees
contain
the
same
set
of
values,
which
of
the
follo
wing
is
common
bet
w
een
them?
Whichof
the
follo
wing
describes
the
height
of
a
bina
ry
sea
rch
tree
on
n
nodes?
2Red-Black
T
rees
Isthe
follo
wing
a
valid
red-black
tree?
W
e
a
re
not
dra
wing
the
implicit
NIL
nodes.
Isthe
follo
wing
a
valid
red-black
tree?
Isthe
follo
wing
a
valid
red-black
tree?
Whichof
the
follo
wing
describes
the
height
of
a
red-black
tree
on
n
nodes?
Ifthe
length
of
a
path
from
the
root
of
a
red-black
tree
to
one
of
the
leaf
NIL
nodes
is
100
,what
could
be
the
length
of
another
path
from
the
root
to
some
other
NIL
node?
Supposethat
r
isthe
root
of
a
red-black
tree
on
n
nodes.Assume
all
nodes
have
distinct
values.
If
w
e
so
rt
the
values
sto
red
in
the
tree
to
get
x
1
<x
2
<
··
·
<x
n
,and
find
the
index
i
where
r
=
x
i
,what
can
be
said
about
i
?
Whatis
the
w
o
rst-case
runtime
of
operations
INSERT/DELETE/SEARCH
on
a
red-black
tree
sto
ring
n
nodes?