Implement the preorder tree walk() and postorder tree walk() functions

__________________________________________________-

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(" ");

}

}