Implement the inorder tree walk() function Implement the search() function Imple
ID: 3590894 • Letter: I
Question
Implement the inorder tree walk() function
Implement the search() function
Implement the iterative search()
Implement the minimum() function
Implement the maximum() function
Implement the successor() function
Implement the insert() function
***post screenshots of code too please****
package ds;
public class BinarySearchTree {
public TreeNode root;
public BinarySearchTree () {
root = null;
}
public void inorder_tree_walk (TreeNode x) {
}
public TreeNode search (TreeNode x, int k) {
}
public TreeNode iterative_search (int k) {
}
public TreeNode minimum () {
}
public TreeNode maximum () {
}
public TreeNode successor (TreeNode x) {
}
public void insert (int k) {
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};
BinarySearchTree bst;
TreeNode n;
bst = new BinarySearchTree();
for (int i = 0; i < array.length; i++)
bst.insert(array[i]);
System.out.println("Inorder_tree_walk starts ------------
------");
bst.inorder_tree_walk(bst.root);
System.out.println("Inorder_tree_walk ends --------------
----");
System.out.print(" ");
System.out.println("Search starts ------------------");
n = bst.search(bst.root, 13);
System.out.println("found: " + n.key);
System.out.println("Search ends ------------------");
System.out.print(" ");
System.out.println("Iterative search starts -------------
-----");
n = bst.iterative_search(4);
System.out.println("found: " + n.key);
System.out.println("Iterative search ends ---------------
---");
System.out.print(" ");
System.out.println("Minimum starts ------------------");
n = bst.minimum();
System.out.println("Minimum key is " + n.key);
System.out.println("Minimum ends ------------------");
System.out.print(" ");
System.out.println("Maximum starts ------------------");
n = bst.maximum();
System.out.println("Maximum key is " + n.key);
System.out.println("Maximum ends ------------------");
System.out.print(" ");
System.out.println("Successor starts ------------------
");
n = bst.successor(bst.root.left.right.right);
System.out.println("Successor key is " + n.key);
System.out.println("Successor ends ------------------");
System.out.print(" ");
}
}
Explanation / Answer
/*******************************TreeNode.java************************************/
package ds;
/**
* The Class TreeNode.
*/
public class TreeNode {
/** The data. */
private int key;
/** The left. */
private TreeNode left;
/** The right. */
private TreeNode right;
/** The parent. */
private TreeNode parent;
/**
* Instantiates a new tree node.
*
* @param key
* the key
* @param left
* the left
* @param right
* the right
*/
public TreeNode(int key, TreeNode left, TreeNode right) {
this.key = key;
this.left = left;
this.right = right;
}
/**
* Gets the data.
*
* @return the data
*/
public int getKey() {
return key;
}
/**
* Sets the data.
*
* @param key
* the new key
*/
public void setKey(int key) {
this.key = key;
}
/**
* Gets the left.
*
* @return the left
*/
public TreeNode getLeft() {
return left;
}
/**
* Sets the left.
*
* @param left
* the left to set
*/
public void setLeft(TreeNode left) {
this.left = left;
}
/**
* Gets the right.
*
* @return the right
*/
public TreeNode getRight() {
return right;
}
/**
* Sets the right.
*
* @param right
* the right to set
*/
public void setRight(TreeNode right) {
this.right = right;
}
/**
* Gets the parent.
*
* @return the parent
*/
public TreeNode getParent() {
return parent;
}
/**
* Sets the parent.
*
* @param parent the parent to set
*/
public void setParent(TreeNode parent) {
this.parent = parent;
}
}
/***************************************BinarySearchTree.java**************************************************/
package ds;
/**
* The Class BinarySearchTree.
*/
public class BinarySearchTree {
/** The root. */
public TreeNode root;
/**
* Instantiates a new binary search tree.
*/
public BinarySearchTree() {
root = null;
}
/**
* Inorder tree walk.
*
* @param x
* the x
*/
public void inorder_tree_walk(TreeNode x) {
if (x != null) {
inorder_tree_walk(x.getLeft());
System.out.print(x.getKey() + " ");
inorder_tree_walk(x.getRight());
}
}
/**
* Search.
*
* @param x
* the x
* @param k
* the k
* @return the tree node
*/
public TreeNode search(TreeNode x, int k) {
if (x == null)
return null;
else if (k == x.getKey())
return x;
else if (k < x.getKey())
return search(x.getLeft(), k);
else
return search(x.getRight(), k);
}
/**
* Iterative search.
*
* @param k
* the k
* @return the tree node
*/
public TreeNode iterative_search(int k) {
TreeNode temp = this.root;
while (temp != null && k != temp.getKey()) {
if (k < temp.getKey())
temp = temp.getLeft();
else
temp = temp.getRight();
}
return temp;
}
/**
* Minimum.
*
* @return the tree node
*/
public TreeNode minimum() {
TreeNode temp = this.root;
/* loop down to find the leftmost leaf */
while (temp.getLeft() != null) {
temp = temp.getLeft();
}
return temp;
}
/**
* Maximum.
*
* @return the tree node
*/
public TreeNode maximum() {
TreeNode temp = this.root;
/* loop down to find the leftmost leaf */
while (temp.getRight() != null) {
temp = temp.getRight();
}
return temp;
}
/**
* Successor.
*
* @param x
* the x
* @return the tree node
*/
public TreeNode successor(TreeNode x) {
TreeNode temp = this.root;
return inorderSuccessor(temp, x);
}
/**
* Inorder successor.
*
* @param root
* the root
* @param x
* the x
* @return the tree node
*/
public TreeNode inorderSuccessor(TreeNode root, TreeNode x) {
// step 1 of the above algorithm
if (x.getRight() != null) {
return minValue(x.getRight());
}
// step 2 of the above algorithm
TreeNode p = x.getParent();
while (p != null && x == p.getRight()) {
x = p;
p = p.getParent();
}
return p;
}
/**
* Min value.
*
* @param node
* the node
* @return the tree node
*/
private TreeNode minValue(TreeNode node) {
TreeNode temp = node;
/* loop down to find the leftmost leaf */
while (temp.getLeft() != null) {
temp = temp.getLeft();
}
return temp;
}
/**
* Insert.
*
* @param k
* the k
*/
public void insert(int k) {
TreeNode node = new TreeNode(k, null, null);
insertRecursive(node, root);
}
/**
* Insert recursive.
*
* @param node
* the node
* @param root
* the root
*/
private void insertRecursive(TreeNode node, TreeNode root) {
if (root == null) {
this.root = node;
return;
}
if (node.getKey() < root.getKey())
if (root.getLeft() == null) {
node.setParent(root);
root.setLeft(node);
} else
insertRecursive(node, root.getLeft());
else if (root.getRight() == null) {
node.setParent(root);
root.setRight(node);
} else
insertRecursive(node, root.getRight());
}
/**
* The main method.
*
* @param args
* the arguments
*/
public static void main(String[] args) {
int[] array = { 15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9 };
BinarySearchTree bst;
TreeNode n;
bst = new BinarySearchTree();
for (int i = 0; i < array.length; i++)
bst.insert(array[i]);
System.out.println("Inorder_tree_walk starts ------------------");
bst.inorder_tree_walk(bst.root);
System.out.print(" ");
System.out.println("Inorder_tree_walk ends ------------------");
System.out.print(" ");
System.out.println("Search starts ------------------");
n = bst.search(bst.root, 13);
System.out.println("found: " + n.getKey());
System.out.println("Search ends ------------------");
System.out.print(" ");
System.out.println("Iterative search starts ------------------");
n = bst.iterative_search(4);
System.out.println("found: " + n.getKey());
System.out.println("Iterative search ends ------------------");
System.out.print(" ");
System.out.println("Minimum starts ------------------");
n = bst.minimum();
System.out.println("Minimum key is " + n.getKey());
System.out.println("Minimum ends ------------------");
System.out.print(" ");
System.out.println("Maximum starts ------------------");
n = bst.maximum();
System.out.println("Maximum key is " + n.getKey());
System.out.println("Maximum ends ------------------");
System.out.print(" ");
System.out.println("Successor starts ------------------");
n = bst.successor(bst.root.getLeft().getRight().getRight());
System.out.println("Successor key is " + n.getKey());
System.out.println("Successor ends ------------------");
System.out.print(" ");
}
}
/****************************************output************************************/
Inorder_tree_walk starts ------------------
2 3 4 6 7 9 13 15 17 18 20
Inorder_tree_walk ends ------------------
Search starts ------------------
found: 13
Search ends ------------------
Iterative search starts ------------------
found: 4
Iterative search ends ------------------
Minimum starts ------------------
Minimum key is 2
Minimum ends ------------------
Maximum starts ------------------
Maximum key is 20
Maximum ends ------------------
Successor starts ------------------
Successor key is 15
Successor ends ------------------
Thanks a lot. Please let me know if you have any doubt.