1998 Autumn Paper 2.1 Sect. B Q3(d,e)



Original tree...



                        r Sul

                b Pot <

                        r Pho

        r Nit <

                b Iod

b Hel <

        b Car



Whilst traversing the tree before adding "Oxygen" we perform

some recolouring when we notice that "Potassium" has two red

children...



                        b Sul

                r Pot <

                        b Pho

        r Nit <

                b Iod

b Hel <

        b Car





Rebalancing because the parent of "Potassium" is also red...



                b Sul

        r Pot <

                b Pho

b Nit <

                b Iod

        r Hel <

                b Car





When we reach a NULL, add "Oxygen"...



                b Sul

        r Pot <

                b Pho \

                        r Oxy

b Nit <

                b Iod

        r Hel <

                b Car





Finished.