Show the result of inserting 4 1 2 5 9 7 6 3 into an initial

Show the result of inserting 4, 1, 2, 5, 9, 7, 6, 3 into an initially empty binary search tree. (b) Show the results of deleting the root of the tree.

Solution

inserting 4,1,2,5,9,7,6,3

1. make 4 as root

4

2. next element is 1 so insert it on left of 4

4

/

1

3. Insert 2 to the right of 1

4

/

1

\\

2

4. next element is 5 it is greater than 4 so insert it to the right subtree of 4

4

/ \\

1 5

\\

2

next element is 9

4

/ \\

1 5

\\ \\

2 9

\\ /

3 7

/

6

(b)

4

/ \\

1 5

\\ \\

2 9

\\ /

3 7

/

6

Deleting the root 4 of the tree.

Traverse to the left hand side of the tree and get the highest value. Here highest value in left subtree is 3

swap 4 with 3

3

/ \\

1 5

\\ \\

2 9

/

7

/

6