CareerCup

Rows represent the ancestors and columns represent the children

Hence Root Node is the column with all zeros

Step1. find root node O(m*n)
Step2. using depth first traversal reconstruct the tree O(m*n)

total time = O(m*n)

Node createTree(int[][] m){
	if(m.length == 0) return null;

	//find root node
	int r = findRoot(m);
	
	if(r == -1) return null;
	Node rn = makeTree(m, r);
}

Node makeTree(int[][] m, r) {
	Node curr = new Node(r);
	ArrayList<Node> children = null;
	
	for(int col=0; col < m[0].length; col++){
		if(m[r][col] == 1){
			Node child = makeTree(m, col);
			if(children == null){
				children = new ArrayList<Node>();
			}
			children.add(child);
		}
	}
	return curr;
}

//return root node or -1 if invalid matrix
// that is if there is a loop in the graph/tree
// or more than one ancestor for a node
int findRoot(int[][] m) {
	int root = -1;
	boolean alreadyFound = false;
	for(int col=0; i < m[0].length;col++) 
		int count = 0;
		for(int row=0; row < m.length; row++) {
			count = count + m[col][row];
		}
		if(count == 0) {
			//more then one root node
			if(alreadyFound) return -1;
			alreadyFound = true;
			root = col;
		}
		if(count > 1){
			//some node has more than one parent
			return -1;
		}
	}
	return root;
}

Looks like a topological sort question.

A tree data structure is such that a node can have only 1 parents, all nodes are connected and no cycles [Wiki is my source].

Leet, your first step is correct to find the root. Then you can simply start with the root and find all its children, connect them to root and also push them to queue. As long as queue is not empty, remove first element from queue, add all its children and push its children to the queue. In the end you will have a tree. [Basically this is kind of reverse BFS]

Why? Since all nodes are connected, you will find all nodes as you traverse the above algorithm. Since all nodes have only one parent, they are pushed into the queue only once and processed only once.

public class BuildTreeFromAncesterMatrix {
public static final int[][] matrix = new int[][] {
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 0, 0 ,0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};

public static final int size = 5;
public static final int ary = 3;

public class TreeNode {
public TreeNode(int name) {
this.name = name;
}
public TreeNode[] children = new TreeNode[ary];
public int name;
}

@Test
public void test() {
printSubTree(buildTree());
}

public void printSubTree(TreeNode node) {
String str;
str = node.name + " children: ";
int index = 0;
while(node.children[index++] != null) {
str += node.children[index -1].name + " ";
printSubTree(node.children[index -1]);
}
System.out.println(str);
}

public TreeNode buildTree() {
TreeNode[] nodes = new TreeNode[size];
for (TreeNode n : nodes) {
n = null;
}
int[] head = new int[size];
for (int i = 0; i < size; ++i) {
leave(nodes, i, head);
}
TreeNode headNode = null;
for (int j : head) {
if (j == 0)
headNode = nodes[j];
}
return headNode;
}


public TreeNode leave(TreeNode[] nodes, int i, int[] head) {
if (nodes[i] != null) return nodes[i];
nodes[i] = new TreeNode(i);
int index = 0;
for (int j = 0; j < size; ++j) {
if (matrix[i][j] == 1) {
head[j] = 1;
nodes[i].children[index++] = leave(nodes, j, head);
}
}
return nodes[i];
}

public class BuildTreeFromAncesterMatrix {
public static final int[][] matrix = new int[][] {
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 0, 0 ,0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};

public static final int size = 5;
public static final int ary = 3;

public class TreeNode {
public TreeNode(int name) {
this.name = name;
}
public TreeNode[] children = new TreeNode[ary];
public int name;
}

@Test
public void test() {
printSubTree(buildTree());
}

public void printSubTree(TreeNode node) {
String str;
str = node.name + " children: ";
int index = 0;
while(node.children[index++] != null) {
str += node.children[index -1].name + " ";
printSubTree(node.children[index -1]);
}
System.out.println(str);
}

public TreeNode buildTree() {
TreeNode[] nodes = new TreeNode[size];
for (TreeNode n : nodes) {
n = null;
}
int[] head = new int[size];
for (int i = 0; i < size; ++i) {
leave(nodes, i, head);
}
TreeNode headNode = null;
for (int j : head) {
if (j == 0)
headNode = nodes[j];
}
return headNode;
}


public TreeNode leave(TreeNode[] nodes, int i, int[] head) {
if (nodes[i] != null) return nodes[i];
nodes[i] = new TreeNode(i);
int index = 0;
for (int j = 0; j < size; ++j) {
if (matrix[i][j] == 1) {
head[j] = 1;
nodes[i].children[index++] = leave(nodes, j, head);
}
}
return nodes[i];
}

1. Traverse the matrix in row order and calculate the sum of each row.
2. Create lists of row numbers corresponding to every sum. 0 will have only 1 row, 1 will have n row numbers, and so on. Each of these lists now represent the levels of n-ary tree.
3. Now start with list with sum 0 and create root node. Add all row numbers contained in list sum 1 as children of the root node.
4. Now set root node column to 0 for all rows. So level 2 rows will just have their parent's column set as 1. For all level 2 rows find the only column set as 1 and add current row as a child of that node.

Repeat for all levels.

Simple way:

1. Calculate the sum of each row. and wave it in an array.(0(n2))

Now Loop into this arr ( till you hit all the non zero elements (O(n2)))
1. each time find for least element and delete that element from array.
2. take the node which corresponds to the selected element from the array.
3. Add all its children if the are not added to any of the other nodes earlier.