Binary Tree Peers. Everything is public for simplicity
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); | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment