public class Node {
        public int value;
        public Node left;
        public Node right;
        public Node peer;

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

        public String peerMessage() {
            return value + "'s peer -> " + (peer != null ? peer.value : "null");
        }
    }

    public Node fillChildPeers(Node node) {
        if (node == null) {
            return null;
        }
        if (node.left != null) {
            if (node.right != null) {
                node.left.peer = node.right;
                System.out.println(node.left.peerMessage());
            } else {
                node.left.peer = findPeerFromParentPeerThatHasChild(node);
                System.out.println(node.left.peerMessage());
            }

        }
        if (node.right != null) {
            node.right.peer = findPeerFromParentPeerThatHasChild(node);
            System.out.println(node.right.peerMessage());
        }

        fillChildPeers(node.left);
        fillChildPeers(node.right);

        return node;
    }

    public Node findPeerFromParentPeerThatHasChild(Node node) {
        if (node.peer == null) {
            return null;
        }
        if (node.peer.left != null) {
            return node.peer.left;
        }
        if (node.peer.right != null) {
            return node.peer.right;
        }
        return findPeerFromParentPeerThatHasChild(node.peer);
    }

    /**
     *
     *                (0)                           1's peer -> 2
     *               /  \                           2's peer -> null
     *             (1)--(2)                         3's peer -> 4
     *            / \    \            expected      4's peer -> 5
     *          (3)-(4)--(5)                        5's peer -> null
     *         /          \                         6's peer -> 7
     *       (6)----------(7)                       7's peer -> null
     *      /                                       8's peer -> null
     *    (8)
     */

    @Test
    public void nodeTest() {
        Node root = new Node(0);
        Node one = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3);
        Node four = new Node(4);
        Node five = new Node(5);
        Node six = new Node(6);
        Node seven = new Node(7);
        Node eight = new Node(8);

        root.left = one;
        root.right = two;
        one.left = three;
        one.right = four;
        two.right = five;

        three.left = six;
        five.right = seven;
        six.left = eight;

        root = fillChildPeers(root);
        Assert.assertEquals(one.peer.value, 2);
        Assert.assertEquals(two.peer, null);
        Assert.assertEquals(three.peer.value, 4);
        Assert.assertEquals(four.peer.value, 5);
        Assert.assertEquals(five.peer, null);
        Assert.assertEquals(six.peer.value, 7);
        Assert.assertEquals(seven.peer, null);
        Assert.assertEquals(eight.peer, null);
    }