Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.