2
\$\begingroup\$

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

    public void addElement(int element) {
        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;
        }
    }
  }
\$\endgroup\$
  • 1
    \$\begingroup\$ I assume that this is Java, given your Username? I added the tag. \$\endgroup\$ – Malachi Oct 31 '13 at 18:01
2
\$\begingroup\$
  • 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.
  • You can make your class generic but that's not a big deal for now but in future keep this in head and try to find always general solution for any given problem.
  • 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?

Otherwise your code is good and self-documenting.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.