# Finding inorder successor

I want you to pick my code apart and give me some feedback on how I could make it better or more simple. This code finds inorder successor in a binary tree.

public class Successor {

private TreeNode root;

private class TreeNode {
TreeNode left;
TreeNode right;
TreeNode parent;
int item;

TreeNode(TreeNode left, TreeNode right, TreeNode parent, int item) {
this.left = left;
this.right = right;
this.parent = parent;
this.item = item;
}
}

public void makeBinarySearchTree(int[] a) {
for (int i : a) {
}
}

if (root == null) {
root = new TreeNode(null, null, null, element);
} else {
TreeNode prevNode = null;
TreeNode node = root;

while (node != null) {
prevNode = node;
// no definition exists, and for convenience we will stick to this one.
if (element < node.item) {
node = node.left;
} else {
node = node.right;
}
}

if (element < prevNode.item) {
prevNode.left = new TreeNode(null, null, prevNode, element);
} else {
prevNode.right = new TreeNode(null, null, prevNode, element);
}
}
}

private TreeNode search (int x) {
TreeNode node = root;

while (node != null) {
if (x < node.item) {
node = node.left;
} else if (x  > node.item) {
node = node.right;
} else {
return node;
}
}

return null;
}

public Integer getSucessor(int val) {
TreeNode node = getInorderSuccessor(search(val));
return node == null ? null : node.item;
}

private TreeNode getInorderSuccessor(TreeNode node) {
if (node == null) return null;

if (node.right != null) {
node = node.right;
while (node.left != null) {
node = node.left;
}
return node;
} else {
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
}
}

• I assume that this is Java, given your Username? I added the tag. – Malachi Oct 31 '13 at 18:01

• Please give clear meaningful name. Your class name is Successor... now who's successor? yours? king Luthar's? who's? See the concern. I think BinarySearchTree is the apt. name for the class.
• In makeBinarySearchTree you are creating a Binary Tree, so someone seeing your code will think it as a factory method, so better make it that way.
• Someone using your getSucessor method(should be getSuccessor) will always get the inorder-successor. Now what if someday someone want to find preorder-successor or preorder-successor, what will you do then?