Create a binary search tree class. This class should have the followings: A data
ID: 664986 • Letter: C
Question
Create a binary search tree class. This class should have the followings:
A data member that points to the root node of the tree
A constructor that takes an int[] array as argument and build the BST from the array (each
node is an object created from class Node in problem 1)
An iterativeSearch method that can be used to search for a node with the given key value
A insert method to insert a node into the tree
A successor method that finds the successor for a given node
A minimum method that finds the minimum value in any of the subtrees, given a node x (not
just from the root and not just the minimum of the entire input array)
An inorderTreeWalk method that can be used to display the results from the in-order tree
walk, starting from any given node
Explanation / Answer
Complete Program:
// File: BinarySearchTree.java
public class BinarySearchTree
{
private class Node
{
public int key;
public Node left;
public Node right;
public Node p;
public Node(int newKey)
{
key = newKey;
left = null;
right = null;
p = null;
}
}
public Node root;
public BinarySearchTree(int[] arr)
{
root = null;
for(int i = 0; i < arr.length; i++)
insert(this, new Node(arr[i]));
}
public Node iterativeSearch(Node x, int key)
{
while(x != null && key != x.key)
{
if(key < x.key)
x = x.left;
else
x = x.right;
}
return x;
}
public void insert(BinarySearchTree T, Node z)
{
Node y = null;
Node x = T.root;
while(x != null)
{
y = x;
if(z.key < x.key)
x = x.left;
else
x = x.right;
}
z.p = y;
if(y == null)
T.root = z;
else if(z.key < y.key)
y.left = z;
else
y.right = z;
}
public Node successor(Node x)
{
if(x.right != null)
return minimum(x.right);
Node y = x.p;
while(y != null && x == y.right)
{
x = y;
y = y.p;
}
return y;
}
public Node minimum(Node x)
{
while(x.left != null)
x = x.left;
return x;
}
public void inorderTreeWalk(Node x)
{
if(x != null)
{
inorderTreeWalk(x.left);
System.out.print(x.key + " ");
inorderTreeWalk(x.right);
}
}
public void inorderTreeWalk()
{
inorderTreeWalk(root);
}
public static void main(String[] args)
{
int[] arr = {45, 36, 57, 42, 61, 55, 39, 25};
BinarySearchTree tree = new BinarySearchTree(arr);
System.out.print(" Keys in the tree by inorder: ");
tree.inorderTreeWalk();
}
}
----------------------------------------------------------------------
Sample Output:
Keys in the tree by inorder: 25 36 39 42 45 55 57 61