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

The variable root refers to the root node of the tree. If the tree is empty, root is null . The
following code creates the first three nodes of the tree in Figure 25.3.

// Create the root node
TreeNode<Integer> root = new TreeNode<>( 60 );

// Create the left child node
root.left = new TreeNode<>( 55 );

// Create the right child node
root.right = new TreeNode<>( 100 );

25.2.2 Searching for an Element
To search for an element in the BST, you start from the root and scan down from it until a
match is found or you arrive at an empty subtree. The algorithm is described in Listing 25.1.
Let current point to the root (line 2). Repeat the following steps until current is null (line
4) or the element matches current.element (line 12).

If element is less than current.element , assign current.left to current
(line 6).

■

If element is greater than current.element , assign current.right to
current (line 9).

■

If element is equal to current.element , return true (line 12).

■

If current is null , the subtree is empty and the element is not in the tree (line 14).

L ISTING 25.1

Searching for an Element in a BST
1 public boolean search(E element) {
2 TreeNode<E> current = root; // Start from the root
3
4 while (current != null )
5 if (element < current.element) {
6 current = current.left; // Go left
7 }
8 else if (element > current.element) {
9 current = current.right; // Go right
10 }
11

start from root

left subtree

right subtree

else // Element matches current.element

12 return true ; // Element is found found

13
14

return false ; // Element is not in the tree

not found

15 }

25.2.3 Inserting an Element into a BST
To insert an element into a BST, you need to locate where to insert it in the tree. The key idea
is to locate the parent for the new node. Listing 25.2 gives the algorithm.

L ISTING 25.2

Inserting an Element into a BST
1 boolean insert(E e) {
2 if (tree is empty)
3 // Create the node for e as the root;
4 else {
5 // Locate the parent node
6 parent = current = root;
7

create a new node

while (current != null ) locate parent