I created functions that are able to get the successor Node in a binary search tree traversing it in all 3 ways, in order, post order, and pre order. My challenge now is try to put them all in a getNextItem method, and call each of those aforementioned functions using the getNextItem method. I know what the skeleton of the getNextItem method should be I just don't know how to complete it. I also included the insert and main method if anyone wanted to test my functions. Please note I cannot change the parameters in the getNextItem method.
public class BinaryTree {
public static final int INORDER = 1;
public static final int PREORDER = 2;
public static final int POSTORDER = 3;
TreeNode root;
TreeNode currentNode;
class TreeNode {
int data;
TreeNode left, right, parent, root;
TreeNode(int data) {
this.data = data;
left = right = parent = root = null;
}
}
TreeNode insert(TreeNode node, int data) {
if (node == null) {
return (new TreeNode(data));
}
else {
TreeNode temp = null;
if (data <= node.data) {
temp = insert(node.left, data);
node.left = temp;
temp.parent = node;
}
else {
temp = insert(node.right, data);
node.right = temp;
temp.parent = node;
}
return node;
}
}
public Comparable getNextItem(int orderType) {
switch (orderType) {
case INORDER:
break;
case PREORDER:
break;
case POSTORDER:
break;
return;
}
TreeNode inOrderSuccessor(TreeNode n) {
if (n.right != null) {
return minValue(n.right);
}
TreeNode p = n.parent;
while (p != null && n == p.right) {
n = p;
p = p.parent;
}
return p;
}
TreeNode minValue(TreeNode node) {
TreeNode current = node;
while (current.left != null) {
current = current.left;
}
return current;
}
TreeNode preorderSuccessor(TreeNode n) {
if (n.left != null)
return n.left;
if (n.right != null)
return n.right;
TreeNode curr = n, parent = curr.parent;
while (parent != null && parent.right == curr) {
curr = curr.parent;
parent = parent.parent;
}
if (parent == null)
return null;
return parent.right;
}
TreeNode postorderSuccessor(TreeNode n) {
if (n == null)
return null;
TreeNode parent = n.parent;
if (parent.right == null || parent.right == n)
return parent;
TreeNode curr = parent.right;
while (curr.left != null)
curr = curr.left;
return curr;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
TreeNode root = null, temp = null, suc = null, suc2 = null, suc3 = null, min = null;
root = tree.insert(root, 20);
root = tree.insert(root, 8);
root = tree.insert(root, 22);
root = tree.insert(root, 4);
root = tree.insert(root, 12);
root = tree.insert(root, 10);
root = tree.insert(root, 14);
temp = root.left.right.right;
suc = tree.inOrderSuccessor(temp);
System.out.println(
"Inorder successor of "
+ temp.data + " is " + suc.data);
suc = tree.preorderSuccessor(temp);
System.out.println(
"Preorder successor of "
+ temp.data + " is " + suc.data);
suc = tree.postorderSuccessor(temp);
System.out.println(
"Postorder successor of "
+ temp.data + " is " + suc.data);
}
}
I would suggest starting with currentNode = null, so that the very first call of getNextItem will actually return the data of the very first node in the given traversal order.
I would also have the class manage its root member itself, so that the main program does not have to update it after calling insert.
The name minValue is not really representative of what it does, as it does not return a node's value, but a node. It could be a method on the TreeNode class.
Here is how it could look:
class BinaryTree {
public static final int INORDER = 1;
public static final int PREORDER = 2;
public static final int POSTORDER = 3;
TreeNode root, currentNode;
public class TreeNode {
int data;
TreeNode left, right, parent;
public TreeNode(int data) {
this.data = data;
left = right = parent = null; // There should be no root here.
}
TreeNode minNode() {
return left == null ? this : left.minNode();
}
}
public BinaryTree() {
root = null;
}
public void insert(int newData) {
root = root == null ? new TreeNode(newData) : insert(root, newData);
}
private TreeNode insert(TreeNode node, int newData) {
if (node == null) return new TreeNode(newData);
if (newData < node.data) {
node.left = insert(node.left, newData);
node.left.parent = node;
} else if (newData > node.data) {
node.right = insert(node.right, newData);
node.right.parent = node;
}
return node;
}
private TreeNode inOrderSuccessor(TreeNode node) {
if (node == null) return root.minNode();
if (node.right != null) return node.right.minNode();
while (node.parent != null) {
if (node == node.parent.left) return node.parent;
node = node.parent;
}
return null;
}
private TreeNode preOrderSuccessor(TreeNode node) {
if (node == null) return root;
if (node.left != null) return node.left;
if (node.right != null) return node.right;
while (node.parent != null) {
if (node == node.parent.left && node.parent.right != null) {
return node.parent.right;
}
node = node.parent;
}
return null;
}
private TreeNode postOrderSuccessor(TreeNode node) {
if (node == null) return root.minNode();
if (node.parent == null) return null;
if (node.parent.right == node || node.parent.right == null) return node.parent;
node = node.parent.right;
while (node.left == null && node.right != null) {
node = node.right;
}
return node.minNode();
}
public Comparable getNextItem(int orderType) {
if (root == null) return null;
switch (orderType) {
case INORDER:
currentNode = inOrderSuccessor(currentNode);
break;
case PREORDER:
currentNode = preOrderSuccessor(currentNode);
break;
case POSTORDER:
currentNode = postOrderSuccessor(currentNode);
break;
}
return currentNode == null ? null : currentNode.data;
}
public void reset() {
currentNode = null;
}
void print() {
print(root, "");
}
void print(TreeNode node, String tab) {
if (node == null) return;
print(node.right, tab + " ");
System.out.println(tab + node.data);
print(node.left, tab + " ");
}
public static void main(String[] args) {
Main tree = new BinaryTree();
tree.insert(8);
tree.insert(3);
tree.insert(10);
tree.insert(9);
tree.insert(1);
tree.insert(6);
tree.insert(7);
tree.print();
tree.reset();
System.out.println("In-order traversal:");
while (true) {
Comparable data = tree.getNextItem(INORDER);
if (data == null) break;
System.out.print(data + " ");
}
System.out.println();
tree.reset();
System.out.println("Pre-order traversal:");
while (true) {
Comparable data = tree.getNextItem(PREORDER);
if (data == null) break;
System.out.print(data + " ");
}
System.out.println();
tree.reset();
System.out.println("Post-order traversal:");
while (true) {
Comparable data = tree.getNextItem(POSTORDER);
if (data == null) break;
System.out.print(data + " ");
}
System.out.println();
}
}