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

114 protected TreeNode<E> right;

115
116 public TreeNode(E e) {
117 element = e;
118 }
119 }
120
121 @Override /** Get the number of nodes in the tree */
122 public int getSize() {

getSize

123 return size;

124 }
125
126

/** Returns the root of the tree */

127 public TreeNode<E> getRoot() {

getRoot

128 return root;

129 }
130
131 /** Returns a path from the root leading to the specified element */
132 public java.util.ArrayList<TreeNode<E>> path(E e) {
133 java.util.ArrayList<TreeNode<E>> list =
134 new java.util.ArrayList<>();
135 TreeNode<E> current = root; // Start from the root
136
137 while (current != null ) {
138 list.add(current); // Add the node to the list
139 if (e.compareTo(current.element) < 0 ) {
140 current = current.left;
141 }
142 else if (e.compareTo(current.element) > 0 ) {
143 current = current.right;
144 }
145

path

else

146 break ;

147 }
148
149 return list; // Return an array list of nodes

150 }
151
152 @Override /** Delete an element from the binary search tree.
153 * Return true if the element is deleted successfully.
154 * Return false if the element is not in the tree. */
155 public boolean delete(E e) {
156 // Locate the node to be deleted and also locate its parent node
157 TreeNode<E> parent = null ;
158 TreeNode<E> current = root;
159 while (current != null ) {
160 if (e.compareTo(current.element) < 0 ) {
161 parent = current;
162 current = current.left;
163 }
164 else if (e.compareTo(current.element) > 0 ) {
165 parent = current;
166 current = current.right;
167 }
168

delete

locate parent
locate current

else

169 break ; // Element is in the tree pointed at by current

current found

170 }
171
172

if (current == null )

not found

173 return false ; // Element is not in the tree