Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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.
I probably don't understand, but when you "find all its children", aren't you also bound to find grandchildren? In other words, assuming that you mean that for a root whose row == r, if you find all m[r][j] == 1, you will find all of the grandchildren and great grandchildren, etc as well, right? Do you connect them to root and push them to queue as well?
It seems like the other solutions listed here also do not take this into account, so maybe there is something I am missing. Thanks.
when you find the root,set the matrix[row][root] =0 nad the row of of root as -1,find the rows with all zeroes to find the children
Just a thought. Pls provide your comments.
How about putting in the Queue during BFS of the tree the <children,parent> pair when we traverse the adjacent list of parent. So that when we dequeue from the Q, it becomes easy to connect the dequeued node to the parent easily without any confusion. Else we will have to search over n over again to find the correct parent of the node with the provided matrix.
Few observations i found while looking at the matrix.
No of 1s in the column denotes the level of a given node.
This could be used to speed up or understand the finding of next nodes to be put in the queue.
e.g. column with 0 1's is the root and the column with 2 1's are level 2 and so on.
Why do you need a queue for it? Can't you just recurse? I know it will utilize the stack. But writing code would be simpler.
1) Create a node
2) Iterate through the node's row in matrix
3) recursively call the function to create the node.
4) Add the completed child to the child list
we can get away with queues
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.
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)
- Praveen Kumar July 19, 2012