Adobe Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
firstly number all nodes of tree as you have to form a n*n matrix where n is number of nodes in this given tree, now put all zeros in ith row of matrix where i is the number given to root node,now move onto childrens of this root node level order wise will be favoured now for the jth and kth row put all elements to zero except ith element as i is ancestor of both j and k.now let l be child of k ,then put all elements zero except where jth row is non zero and at position j.do this recursively .
Matrix[leftNode][rightNode]=rootNode...
Tail recursion:
public static Node populateAncestorMatrix(final Node root, final int level) {
if (root == null) {
return null;
}
Node nodeLeft = new Node(-1);
Node nodeRight = new Node(-1);
if (root.left != null) {
nodeLeft = populateAncestorMatrix(root.left, level + 1);
}
if (root.right != null) {
nodeRight = populateAncestorMatrix(root.right, level + 1);
}
if (!ancestorMatrix.containsKey(nodeLeft)) {
ancestorMatrix.put(nodeLeft, new HashMap<Node, Node>());
}
ancestorMatrix.get(nodeLeft).put(nodeRight, root);
return root;
}
First count the total no. of nodes in the tree to allocate the matrix
We can do iterative inorder traversal using Queue.
At any time, if we go upwards, it means all the nodes on this path has been traced and we need to fill the ancestor matrix.
now we iterate all nodes in the queue and mark it as the ancestor of the deepest node.
Here we assume that every node is labelled with a positive integer.
Time Complexity :- O(N) [inorder traversal] + O(NlogN) [marking the elements of matrix]
Space Complexity :- O(LogN) [for Queue] + O(N^2) for matrix
Head recursion:
public void populateAncestorMatrixHeadRecursion(final Node root) {
if (root == null) {
return;
}
if ((root.left != null) && (root.right != null)) {
if (!ancestorMatrix.containsKey(root.left)) {
ancestorMatrix.put(root.left, new HashMap<Node, Node>());
}
ancestorMatrix.get(root.left).put(root.right, root);
} else if ((root.left != null) && (root.right == null)) {
if (!ancestorMatrix.containsKey(root.left)) {
ancestorMatrix.put(root.left, new HashMap<Node, Node>());
}
ancestorMatrix.get(root.left).put(new Node(-1), root);
} else if ((root.left == null) && (root.right != null)) {
Node nullNode = new Node(-1);
if (!ancestorMatrix.containsKey(nullNode)) {
ancestorMatrix.put(nullNode, new HashMap<Node, Node>());
}
ancestorMatrix.get(nullNode).put(root.right, root);
}
if (root.left != null) {
populateAncestorMatrixHeadRecursion(root.left);
}
if (root.right != null) {
populateAncestorMatrixHeadRecursion(root.right);
}
}
}
class Node
{
int data;
public int Data
{
get { return data; }
set { data = value; }
}
public Node left;
public Node right;
public Node(int data)
{
this.data = data;
}
}
static void Main(string[] args)
{
Node t = new Node(3);
t.left = new Node(2);
t.left.left = new Node(1);
t.right = new Node(5);
t.right.left = new Node(4);
int[,] M = new int[5,5];
BuildAncestorTree(t, new List<Node>(),M);
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
Console.Write(M[i,j]);
Console.Write(" ");
}
Console.WriteLine();
}
Console.Read();
}
static void BuildAncestorTree(Node n, List<Node> nodes, int[,] M)
{
if (n != null)
{
nodes.Add(n);
BuildAncestorTree(n.left,nodes,M);
BuildAncestorTree(n.right,nodes,M);
Node cur = nodes[nodes.Count-1];
nodes.Remove(cur);
foreach (Node node in nodes)
{
int i = cur.Data -1;
int j = node.Data -1;
M[i,j] = 1;
}
}
}
# define MAX 10
int a[MAX][MAX]={0};
void AMatrix(int a[][n], struct node* root, int temp[], int index){
if(root == NULL)
return ;
int i;
for(i=0;i< index;i++)
a[root->data][temp[i]]=1;
temp[index]=root->data;
AMatrix(a, root->left, temp, index+1);
AMatrix(a, root->right, temp, index+1);
}
POint out if anything seems incorrect.
Thanks
what is ancestor matrix?
- Anonymous September 02, 2012