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