Question : Given an binary tree, there is only one extra edge. Removing this edge will make it a valid binary tree. Please design an algorithm to find this extra edge.
I struggled with the definition at first. I asked what makes a binary tree valid. Basically, a parent node can only point to left and right, therefore, a child node can only have one parent.
I was then asked to implement a TreeNode. After which I wrote an algorithm that deletes the invalid node.
public class TreeNode {
int data;
TreeNode right;
TreeNode left;
public TreeNode(int data){
this.data = data;
}
}
public TreeNode removeEdge(TreeNode root) {
if(root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
Map<TreeNode, TreeNode> visited = new HashMap<>();
queue.add(root);
while(!queue.isEmpty()) {
TreeNode parent = queue.remove();
TreeNode left = parent.left;
TreeNode right = parent.right;
if(visited.containsKey(left)){
left = null;
} else {
if(left != null) visited.put(left , parent);
}
if(visited.containsKey(right)) {
right = null;
} else {
if(right != null) visited.put(right , parent);
}
if(left != null){
queue.add(child .left);
}
if(right != null){
queue.add(child.right);
}
}
}
Comments (2)
