Google Interview Question
InternsCountry: United States
Interview Type: Phone Interview
use a dfs, dfs(now, father)
start from the root node, and go to the left until the end. assign father node's right son to the node now's brother pointer .
dfs(node *now,node *father){
if (now == null) return;
if (father == null) dfs(now->left, now);
else {
now->brother = father->right;
dfs(now->left, now);
}
}
dfs(root, null);
I wrote a helper class just to handle the BinaryTree stuff. It's at the end. Also, I believe tail-recursion is not recommended if possible, because it can be quite costly in resources (memory). You might be able to make the case its more readable, but generally recursion is more confusing and so prone to developers making mistakes anyway. I solved it using iteration, which should be more resource efficient.
RESULT
***BEFORE***
1 -left-> 2 || -right-> 3
2 -left-> 4 || -right-> 5
4 -left-> 6 || -right-> 7
6
7
5
3
***AFTER***
1 -left-> 2
2 -left-> 4 || -right-> 3
4 -left-> 6 || -right-> 5
6 || -right-> 7
7
5
3
TransformBinaryTree.java
public class TransformBinaryTree {
public static void main(String[] args) {
BinaryTree seven = new BinaryTree("7", null, null);
BinaryTree six = new BinaryTree("6", null, null);
BinaryTree four = new BinaryTree("4", six, seven);
BinaryTree five = new BinaryTree("5", null, null);
BinaryTree two = new BinaryTree("2", four, five);
BinaryTree three = new BinaryTree("3", null, null);
BinaryTree one = new BinaryTree("1", two, three);
System.out.println("***BEFORE***");
one.prettyPrint();
BinaryTree current = one;
//#1 Find the last left node
while(current.getLeft() != null) {
current = current.getLeft();
}
//#2 Now make parent's right your right.
while(null != current.getParent()) {
BinaryTree newRight = current.getParent().getRight();
current.setRight(newRight);
current = current.getParent();
}
System.out.println("\n\n***AFTER***");
one.prettyPrint();
}
}
BinaryTree.java
package trees;
/**
* Created by mvagnoni on 10/29/14.
*/
public class BinaryTree {
private String value;
private BinaryTree left;
private BinaryTree right;
private BinaryTree parent;
public BinaryTree() {
this.value = "";
this.left = null;
this.right = null;
this.parent = null;
}
public BinaryTree(String value, BinaryTree left, BinaryTree right) {
this.value = value;
this.left = left;
if(null != left) {
left.setParent(this);
}
this.right = right;
if(null != right) {
right.setParent(this);
}
this.parent = null;
}
public BinaryTree(String value, BinaryTree left, BinaryTree right, BinaryTree parent) {
this.value = value;
this.left = left;
if(null != left) {
left.setParent(this);
}
this.right = right;
if(null != right) {
right.setParent(this);
}
this.parent = parent;
}
public BinaryTree getParent() {
return parent;
}
public void setParent(BinaryTree parent) {
this.parent = parent;
}
public BinaryTree getLeft() {
return left;
}
public void setLeft(BinaryTree left) {
this.left = left;
fixRelationships(right);
}
public BinaryTree getRight() {
return right;
}
public void setRight(BinaryTree right) {
this.right = right;
fixRelationships(right);
}
private void fixRelationships(BinaryTree orphan) {
if(null != orphan) {
if (null != orphan.getParent()) {
if (orphan == orphan.getParent().getLeft()) {
orphan.getParent().setLeft(null);
} else if (orphan == orphan.getParent().getRight()) {
orphan.getParent().setRight(null);
}
}
orphan.setParent(this);
}
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public void prettyPrint() {
if(null != getValue()) {
System.out.print(getValue());
}
if(null != getLeft()) {
System.out.print(" -left-> " + getLeft().getValue());
}
if(null != getRight()) {
System.out.print(" || -right-> " + getRight().getValue());
}
System.out.print("\n");
if(null != getLeft()) {getLeft().prettyPrint();}
if(null != getRight()) {getRight().prettyPrint();}
}
}
- Tester October 29, 2014