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

8 if (e < the value in current.element) {
9 parent = current; // Keep the parent
10 current = current.left; // Go left
11 }
12 else if (e > the value in current.element) {
13 parent = current; // Keep the parent
14 current = current.right; // Go right
15 }
16

left child

right child

else

17 return false ; // Duplicate node not inserted

18
19

// Create a new node for e and attach it to parent

20
21 return true ; // Element inserted

22 }
23 }

If the tree is empty, create a root node with the new element (lines 2-3). Otherwise, locate the
parent node for the new element node (lines 6-17). Create a new node for the element and link
this node to its parent node. If the new element is less than the parent element, the node for the
new element will be the left child of the parent. If the new element is greater than the parent
element, the node for the new element will be the right child of the parent.
For example, to insert 101 into the tree in Figure 25.3, after the while loop finishes in
the algorithm, parent points to the node for 107 , as shown in Figure 25.4a. The new node
for 101 becomes the left child of the parent. To insert 59 into the tree, after the while loop
finishes in the algorithm, the parent points to the node for 57 , as shown in Figure 25.4b. The
new node for 59 becomes the right child of the parent.

root 60 root 60

55 100 55 100

parent parent

45 57 67 107 45 57 67 107

101 59 101

(a) Inserting 101 (b) Inserting 59

F IGURE 25.4

Two new elements are inserted into the tree.

25.2.4 Tree Traversal
Tree traversal is the process of visiting each node in the tree exactly once. There are several
ways to traverse a tree. This section presents inorder , postorder, preorder , depth-first, and
breadth-first traversals.
With inorder traversal , the left subtree of the current node is visited first recursively, then
the current node, and finally the right subtree of the current node recursively. The inorder
traversal displays all the nodes in a BST in increasing order.
With postorder traversal , the left subtree of the current node is visited recursively first,
then recursively the right subtree of the current node, and finally the current node itself. An
application of postorder is to find the size of the directory in a file system. As shown in

tree traversal

inorder traversal

postorder traversal