test1

yandex.java

package test;

public class Test1 {

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

        public Node(int value) {
            this.value = value;
        }

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

        @Override
        public String toString() {
            return "Node{" +
                ", value=" + value +
                '}';
        }
    }

    public static void main(String... arg) {
        Node root = new Node(5);

        Node child3 = new Node(root, 3);
        Node child9 = new Node(root, 9);
        root.left = child3;
        root.right = child9;

        Node child1 = new Node(child3, 1);
        Node child4 = new Node(child3, 4);
        child3.left = child1;
        child3.right = child4;

        Node child7 = new Node(child9, 7);
        Node child11 = new Node(child9, 11);
        child9.left = child7;
        child9.right = child11;

        Node child20 = new Node(child9, 20);
        child11.right = child20;

        System.out.println(findNext(child4));
        System.out.println(findNext(root));
    }

    public static Node findNext(Node current) {
        if (current.right != null) {
            return findNextChild(current.right);
        } else if (current.parent != null) {
            return findNextParent(current, current.parent);
        } else {
            return null;
        }
    }

    public static Node findNextChild(Node child) {
        if (child.left == null) {
            return child;
        } else {
            return findNextChild(child.left);
        }
    }

    public static Node findNextParent(Node child, Node parent) {
        if (parent == null) {
            return null;
        }
        if (child == parent.right) {
            return findNextParent(parent, parent.parent);
        } else {
            return parent;
        }
    }
}