BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 943

root 2

1 4

root George

3 8

Adam Michael 5

Daniel Jones To m 6

7

Peter

(a) (b)

F IGURE 25.9

The BSTs in Listing 25.6 are pictured here after they are created.

25.1

✓ ✓

Show the result of inserting 44 into Figure 25.4b.

Check

25.2

Show the inorder, preorder, and postorder of traversing the elements in the binary
tree shown in Figure 25.1b.

Point

25.3

If a set of elements is inserted into a BST in two different orders, will the two cor-
responding BSTs look the same? Will the inorder traversal be the same? Will the
postorder traversal be the same? Will the preorder traversal be the same?

25.4

What is the time complexity of inserting an element into a BST?

25.5

Implement the search(element) method using recursion.

25.3 Deleting Elements from a BST
To delete an element from a BST, first locate it in the tree and then consider two
cases—whether or not the node has a left child—before deleting the element and
reconnecting the tree.

Key
Point

The insert(element) method was presented in Section 25.2.3. Often you need to delete an
element from a binary search tree. Doing so is far more complex than adding an element into
a binary search tree.
To delete an element from a binary search tree, you need to first locate the node that
contains the element and also its parent node. Let current point to the node that contains the
element in the binary search tree and parent point to the parent of the current node. The
current node may be a left child or a right child of the parent node. There are two cases
to consider.
Case 1: The current node does not have a left child, as shown in Figure 25.10a. In
this case, simply connect the parent with the right child of the current node, as shown in
Figure 25.10b.
For example, to delete node 10 in Figure 25.11a, you would connect the parent of node 10
with the right child of node 10 , as shown in Figure 25.11b.

locating element