Successor (_4_6)

Successor.java

/**
 * Successor: Write an algorithm to find the "next" node (i.e., in-order successor)
 * of a given node in a binary search tree. You may assume that each node has a link to its parent.
 * Hints: #79, #91
 */
public class Successor {
    public static void main(String[] args) {
        Node n6 = new Node(25, null, null, null);
        Node n5 = new Node(13, null, null, null);

        Node n4 = new Node(8, null, null, null);
        Node n3 = new Node(3, null, null, null);

        Node n2 = new Node(20, n5, n6, null);
        Node n1 = new Node(5, n3, n4, null);
        Node r = new Node(10, n1, n2, null);

        n1.setParent(r);
        n2.setParent(r);

        n3.setParent(n1);
        n4.setParent(n1);

        n5.setParent(n2);
        n6.setParent(n2);

        System.out.println(solution1(r));
    }

    public static Node solution1(Node node) {
        if (node == null) return null;

        if (node.getRight() != null) {
            return leftMostChild(node.getRight());
        } else {
            Node q = node;
            Node x = q.getParent();

            while (x != null && node.getLeft() != q) {
                q = x;
                x = x.getParent();
            }
            return x;
        }
    }

    private static Node leftMostChild(Node node) {
        if (node == null) return null;

        while (node.getLeft() != null) {
            node = node.getLeft();
        }

        return node;
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;
    private Node parent;

    public Node() {
    }

    public Node(int value, Node left, Node right, Node parent) {
        this.value = value;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value + " ";
    }
}