class BinarySearchTree
1: //BinarySearchTree.java
3: class BinarySearchTree
4: {
5: private Node root;
7: public BinarySearchTree()
8: {
9: root = null;
10: }
12: public Node getRoot()
13: {
14: return root;
15: }
17: public Node search(int desiredKey)
18: {
19: Node currentNode = root;
20: while (currentNode != null)
21: {
22: // Return the node if the key matches
23: if (currentNode.key == desiredKey)
24: {
25: return currentNode;
26: }
28: // Navigate to the left if the search key is
29: // less than the node's key.
30: else if (desiredKey < currentNode.key)
31: {
32: currentNode = currentNode.left;
33: }
35: // Navigate to the right if the search key is
36: // greater than the node's key.
37: else
38: {
39: currentNode = currentNode.right;
40: }
41: }
43: // The key was not found in the tree.
44: return null;
45: }
47: public void insert(Node node)
48: {
49: // Check if tree is empty
50: if (root == null)
51: {
52: root = node;
53: }
54: else
55: {
56: Node currentNode = root;
57: while (currentNode != null)
58: {
59: if (node.key < currentNode.key)
60: {
61: // If no left child exists, add the new node
62: // here; otherwise repeat from the left child.
63: if (currentNode.left == null)
64: {
65: currentNode.left = node;
66: currentNode = null;
67: }
68: else
69: {
70: currentNode = currentNode.left;
71: }
72: }
73: else
74: {
75: // If no right child exists, add the new node
76: // here; otherwise repeat from the right child.
77: if (currentNode.right == null)
78: {
79: currentNode.right = node;
80: currentNode = null;
81: }
82: else
83: {
84: currentNode = currentNode.right;
85: }
86: }
87: }
88: }
89: }
91: public boolean remove(int key)
92: {
93: Node parent = null;
94: Node currentNode = root;
96: // Search for the node.
97: while (currentNode != null)
98: {
99: // Check if currentNode has a matching key.
100: if (currentNode.key == key)
101: {
102: if (currentNode.left == null && currentNode.right == null)
103: {
104: if (parent == null) // Node is root
105: {
106: root = null;
107: }
108: else if (parent.left == currentNode)
109: {
110: parent.left = null;
111: }
112: else
113: {
114: parent.right = null;
115: }
116: return true; // Node found and removed
117: }
118: else if (currentNode.left != null && currentNode.right == null)
119: {
120: if (parent == null) // Node is root
121: {
122: root = currentNode.left;
123: }
124: else if (parent.left == currentNode)
125: {
126: parent.left = currentNode.left;
127: }
128: else
129: {
130: parent.right = currentNode.left;
131: }
132: return true; // Node found and removed
133: }
134: else if (currentNode.left == null && currentNode.right != null)
135: {
136: if (parent == null) // Node is root
137: {
138: root = currentNode.right;
139: }
140: else if (parent.left == currentNode)
141: {
142: parent.left = currentNode.right;
143: }
144: else
145: {
146: parent.right = currentNode.right;
147: }
148: return true; // Node found and removed
149: }
150: else
151: {
152: // Find successor (leftmost child of right subtree)
153: Node successor = currentNode.right;
154: while (successor.left != null)
155: {
156: successor = successor.left;
157: }
158: currentNode.key = successor.key; // Copy successor to current node
159: parent = currentNode;
160: currentNode = currentNode.right; // Remove successor from right subtree
161: key = successor.key; // Loop continues with new key
162: }
163: }
164: else if (currentNode.key < key) // Search right
165: {
166: parent = currentNode;
167: currentNode = currentNode.right;
168: }
169: else // Search left
170: {
171: parent = currentNode;
172: currentNode = currentNode.left;
173: }
174: }
175: return false; // Node not found
176: }
177: }