Advanced Data Structures - Java Concepts - page 986

tree.add(ÐTomÑ);

tree.add(ÐDickÑ);

tree.add(ÐHarryÑ);

We want to insert a new element Romeo into it.

tree.add(ÐRomeoÑ);

Start with the root, Juliet. Romeo comes after Juliet , so you move to the
right subtree. You encounter the node Tom. Romeo comes before Tom , so you
move to the left subtree. But there is no left subtree. Hence, you insert a new Romeo
node as the left child of Tom (see Figure 10 ).

You should convince yourself that the resulting tree is still a binary search tree. When
Romeo is inserted, it must end up as a right descendant of Juliet Ȍthat is what the
binary search tree condition means for the root node Juliet . The root node doesn't
care where in the right subtree the new node ends up. Moving along to Tom , the right
child of Juliet , all it cares about is that the new node Romeo ends up somewhere
on its left. There is nothing to its left, so Romeo becomes the new left child, and the
resulting tree is again a binary search tree.

Figure 10

Binary Search Tree After Five Insertions

723