This is the second problem in Google Code Jam 2014, Round 1A
This problem is based on all time favorite of interviewers Binary Tree, you need to find out the minimum number of node to delete to make the given binary tree(in graph form, for any connection in X and Y, you can consider X as child of Y or vice verse) as Full Binary Tree.
Problem
A tree is a connected graph with no cycles.
A rooted tree is a tree in which one special vertex is called the root. If there is an edge between X and Y in a rooted tree, we say that Y is a child of X if X is closer to the root than Y (in other words, the shortest path from the root to X is shorter than the shortest path from the root to Y).
A full binary tree is a rooted tree where every node has either exactly 2 children or 0 children.
You are given a tree G with N nodes (numbered from 1 to N). You are allowed to delete some of the nodes. When a node is deleted, the edges connected to the deleted node are also deleted. Your task is to delete as few nodes as possible so that the remaining nodes form a full binary tree for some choice of the root from the remaining nodes.
Input
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains a single integer N, the number of nodes in the tree. The following N-1 lines each one will contain two space-separated integers: Xi Yi, indicating that G contains an undirected edge between Xi and Yi.
Output
For each test case, output one line containing “Case #x: y“, where x is the test case number (starting from 1) and y is the minimum number of nodes to delete from G to make a full binary tree.
Limits
1 ≤ T ≤ 100. 1 ≤ Xi, Yi ≤ N Each test case will form a valid connected tree.
Small dataset
2 ≤ N ≤ 15.
Large dataset
2 ≤ N ≤ 1000.
Sample
| Input | Output |
3 3 2 1 1 3 7 4 5 4 2 1 2 3 1 6 4 3 7 4 1 2 2 3 3 4 |
Case #1: 0 Case #2: 2 Case #3: 1 |
Explanation
In the first case, G is already a full binary tree (if we consider node 1 as the root), so we don’t need to do anything.
In the second case, we may delete nodes 3 and 7; then 2 can be the root of a full binary tree.
In the third case, we may delete node 1; then 3 will become the root of a full binary tree (we could also have deleted node 4; then we could have made 2 the root).
Solution
We can say that
Number of minimum nodes to be deleted = N – Full Binary Tree with max number of nodes
In order to get full binary tree with max number of nodes, we take each node in the graph and calculate the number of nodes in the full binary tree assuming it as the root node.
For any node with only one edge we can say that length of the full binary tree will be 1(it will just be the root node). For other nodes where there are more than one edge, we take pair of two edges and consider one as left and other as right and get the length of the full binary tree formed by them, finally we consider the maximum length among themselves.
Also in order to make it faster, we save the max length of full binary trees formed by root node n, left node l and right node r in the map with key “n,l,r”.
Finally we loop through the map and get the max value in the map, that will give us the length of the max full binary tree possible and return N – that length.
Here is the Java code for Full Binary Tree Problem in Google Code Jam 2014 Round 1A
package codejam2014;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FullBinaryTree {
private int N;
private String[] inputEdges;
private Map<Integer, Node> map;
private Map<String, Integer> rootCountMap = new HashMap<String, Integer>();
public FullBinaryTree(int N, String[] edges) {
this.N = N;
this.inputEdges = edges;
}
private void initNodeMap(){
map = new HashMap<Integer, FullBinaryTree.Node>();
for(int i =1; i <=N; i++){
map.put(i, new Node(i));
}
for(String edge: inputEdges){
String[] nodes = edge.split(" ");
int node1Data = Integer.parseInt(nodes[0]);
int node2Data = Integer.parseInt(nodes[1]);
Node node1 = map.get(node1Data);
Node node2 = map.get(node2Data);
node1.addEdge(node2);
node2.addEdge(node1);
}
}
public int getNodestoDelete(){
initNodeMap();
updateLevelNodes(1);
for(Node node: map.values()){
updateCountAssumingRoot(node);
}
return N-getMaxRootCountValue();
}
private int updateCountAssumingRoot(Node node){
if(node.getfBTreeRootNodeCount() != 0){
return node.getfBTreeRootNodeCount();
}
if(node.getEdges().size() == 1){
rootCountMap.put(node.data+","+node.getEdges().get(0).data+",0", 1);
return 1;
}
int height= 1;
List<Node> edges = node.getEdges();
for(int i =0; i < edges.size(); i++){
for(int j=i+1; j < edges.size(); j++){
Node leftNode = edges.get(i);
Node rightNode = edges.get(j);
leftNode.getEdges().remove(node);
rightNode.getEdges().remove(node);
String key = node.data+","+leftNode.data+","+rightNode.data;
int tempHeight =0;
if(rootCountMap.get(key) != null){
tempHeight = rootCountMap.get(key);
}
else{
int leftHeight = updateCountAssumingRoot(leftNode);
int rightHeight = updateCountAssumingRoot(rightNode);
tempHeight = leftHeight+ rightHeight+1;
rootCountMap.put(key, (tempHeight));
}
if(tempHeight > height){
height = tempHeight;
}
leftNode.addEdge(node);
rightNode.addEdge(node);
}
}
return height;
}
private int getMaxRootCountValue(){
int maxValue = 0;
for(Integer height: rootCountMap.values()){
if(maxValue < height){
maxValue = height;
}
}
return maxValue;
}
private void updateLevelNodes(int level){
for(Node node: map.values()){
if(node.getEdges().size() == level){
node.setfBTreeRootNodeCount(1);
rootCountMap.put(node.data+","+node.getEdges().get(0).data+",", 1);
}
}
}
public static void main(String[] argv) {
try {
long startTime = System.currentTimeMillis();
Reader reader = new FileReader("small.in");
BufferedReader bufReader = new BufferedReader(reader);
String x = bufReader.readLine();
int numOfTestCases = Integer.parseInt(x);
int count = 0;
File file = new File("small.out");
FileWriter writer = new FileWriter(file);
for(count =1; count<= numOfTestCases; count++) {
int N = Integer.parseInt(bufReader.readLine());
String[] edges = new String[N-1];
for(int i=0; i < N-1; i++){
edges[i] = bufReader.readLine();
}
FullBinaryTree fBTree = new FullBinaryTree(N, edges);
String out = ""+fBTree.getNodestoDelete();
writer.write("Case #" + count + ": "+out+"\n");
System.out.println("Case #" + count + ":"+out);
}
writer.close();
System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
} catch (Exception e) {
e.printStackTrace();
}
}
private class Node {
private int data;
private List<Node> edges = new ArrayList<FullBinaryTree.Node>();
private int fBTreeRootNodeCount = 0;
public int getfBTreeRootNodeCount() {
return fBTreeRootNodeCount;
}
public void setfBTreeRootNodeCount(int fBTreeRootNodeCount) {
this.fBTreeRootNodeCount = fBTreeRootNodeCount;
}
Node(int data){
this.data = data;
}
public void addEdge(Node node){
edges.add(node);
}
public List<Node> getEdges(){
return edges;
}
}
}
