Question

Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the given order – consider there alphabetical position for comparison.

a. W, T, N, J, E, B, A

b. W, T, N, A, B, E, J

c. A, B, W, J, N, T, E

d. B, T, E, A, N, W, J

Alphabetical positions: A-1, B-2, E-5, J-10, N-14,T-20,W-23

Answer 1

a. W, T, N, J, E, B, A

W is root

T < W , add in left

N<W , N<T  add in left

J<W , J<T , J<N add in left

E<W , E<T, E<N,E<J add in left

B<W , B<T , B<N , B<J , add in left

A<W , A<T , A<N , A<J , A<B add in left

b. W, T, N, A, B, E, J

W is root

T<W add in left

N<W , N<T add in left

A<W , A<T , A<N add in left

B<W , B<T , B<N , B>A add in right

E<W , E<T , E<N , E>A , E>B  add in right

J<W , J<T , J<N , J>A , J>B , J>E add in right

c. A, B, W, J, N, T, E

A is root

B>A add in right

W>A , W>B add in right

J>A , J>B , J<W add in left

N>A , N>B , N<W , N>J add in right

T>A , T>B , T<W , T>J , T>N , add in right

E>A , E>B , E<W , E<J go left , add in left

d. B, T, E, A, N, W, J

B is root

T>B add in right

E>B ,E<T add in left

A<B add in left

N>B , go right , N<T , N>E add in right

W>B , go right , W>T , add in right

J>B , go right , J<T , go left , J<N add in left