## Amazon Interview Question

Country: India

Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Create a nxn matrix and initialize to -1
2. Normalize the key values, e.g., if the inorder traversal of the nodes are 377, 11, 5, 1055, 3, 8, ... then map them integers starting from 0 to n, (377, 0), (11, 1), (5, 2), (1055, 3), (3, 4), (8, 5), .... You can map the tree nodes instead of keys to integers too, i.e., Instead of HashMap<Integer, Integer>, you can use HashMap<TreeNode, Integer>.
3. Traverse the tree and set the matrix value for the parent

Note that, you can use any tree traversals, inorder, preorder, or postorder, for step 2 and 3.

here is the recursive preorder implementation

``````// initial call
ancestorMatrix(root, null, m, map);

public static void ancestorMatrix(TreeNode node, TreeNode parent, int[][] m, Map<Integer, Integer> map) {
if (node == null) return;

if (parent != null) m[map.get(node.data)][map.get(parent.data)] = parent.data;

ancestorMatrix(node.left, node, m, map);
ancestorMatrix(node.right, node, m, map);
}``````

The time complexity is O(n).

Comment hidden because of low score. Click to expand.
0

Why do you think time complexity is O(n)? Just initializing all the elements to -1 in a nxn matrix takes O(n^2) time.

Comment hidden because of low score. Click to expand.
0

@Epic_coder. O(n) is obviously the time complexity of the function. As you can see I am passing, the matrix and the map as a parameter to the function.

However, if you really wanna be meticulous about it, you can treat the matrix as 1 D and use one of these tricks:

1. eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/
2. stackoverflow.com/questions/10797284/how-to-zero-out-array-in-o1

Comment hidden because of low score. Click to expand.
0
of 2 vote

Assuming
a) NodeNum(node->left) = 2 * NodeNum(node) and
b) NodeNum(node->right) = 2 * Nodeum(node) + 1 and
c) the node can be ancestor of itself

1) initialize array to 0s.

2) a routine below

void updatematrix(bst *root, unsigned int N)
{
unsigned int i = N;
if (root == NULL)
return;
while (i != 0)
{
array[i-1][N-1] = 1;
i = (i >> 1);
}
updatematrix(root->left, 2*N);
updatematrix(root->right, 2*N+1);
}

Comment hidden because of low score. Click to expand.
0
of 2 vote

The ancestor matrix can be calculated as below. You can test the below code:

``````#include <stdio.h>
#include <stdlib.h>

typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *nn=(node_t *)malloc(sizeof(node_t));
nn->data=data;
nn->left=NULL;
nn->right=NULL;
return nn;
}

void findAncestor(node_t *root,int arr[][4],int temp[],int index)
{
if(root==NULL)
return;
int i;
for(i=0;i<index;i++)
arr[root->data][temp[i]]=1;
temp[index]=root->data;
findAncestor(root->left,arr,temp,index+1);
findAncestor(root->right,arr,temp,index+1);
}
int main()
{
node_t *nn=newNode(1);
nn->left=newNode(2);
nn->right=newNode(3);
int temp[4],i,j;
int arr[4][4]={0};
findAncestor(nn,arr,temp,0);
printf("The ancestor matrix is\n");
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
if(arr[i][j]==1)
printf("The ancestor of %d is %d ",i,j);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone tell what is ancestor Matrix?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the question could have been made clearer and the solution would depend on the requirements.
1. If the ancestor matrix is built sparsely, then determining whether a given node is an ancestor of another node would take O(n) time on avg.
2. If the matrix is built densely, then determining whether a given node is an ancestor of the other would take constant time.

Both sparse and dense matrices can be built recursively in a top-down fashion. To build a sparse matrix we will just mark the position of the parent node in the row of the child node.
To build a dense matrix we will have to copy the whole row of the parent node to the row of the child node and also mark the position of the parent node.

``````buildAncestorMatrix(Node childSubtree, Node parent) {

if (parent == null) do-nothing;

1. Copy the row of the parent to the row of the child
2. Mark parent as ancestor in the row of the child

if (childSubtree.leftSubtree != null)
buildAncestorMatrix(childSubtree.leftSubtree, childSubtree);
if (childSubtree.rightSubtree != null)
buildAncestorMatrix(childSubtree.rightSubtree, childSubtree);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If it is a bst, then:
1. In-order traversal of the tree to find the sorted array of node's elements, say arr. Then,

``````ancestor[n-1]=-1;
for(i=0;i<n-1;i++)
ancestor[a[i]]=a[i+1]; //we would like to make a Matrix[n][n], then we get Ancestor[a[i]][a[i+1]]=1 (Ancestor Matrix is initialized to zero for all its entries).``````

This can be done in O(n).

if would like to have a new field in our structure, say ancestor, for every node, then:
1.Store the addresses of the nodes in their in-order traversal in an array, say arr.
2.

``````arr[n-1]->ancestor=NULL;
for(i=0;i<n-1;i++)
arr[i]->ancestor=arr[i+1];``````

However, if the tree is NOT a binary tree, we can use the following (it is O(n^2) though):

``````void Ancestors(int val, struct bst *b, struct bst **cur)
{
if(b)
{
if(b->data>val && ((*cur)==NULL || (*cur)->data>b->data))
(*cur)=b;

Ancestors(val,b->lc,cur);
Ancestors(val,b->rc,cur);
}
}
void FindAncestor(struct bst *b, struct bst *root)
{
if(b)
{
struct bst *cur=NULL;
Ancestors(b->data,root,&cur);
b->ancestor=cur
FindAncestor(b->lc,root);
FindAncestor(b->rc,root);
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public void UpdateAncestorMatrix(Matrix m, TreeNode t, int parent)
{
if (t == null)
return;

if (parent > 0)
{
for (int i = 0;i < m.GetLength(1); i++)
{
m[t.Value, i] = m[parent, i];
}

m[t.Value, parent] = 1;
}

UpdateAncestorMatrix(m, t.Left, t.Value);
UpdateAncestorMatrix(m, t.Right, t.Value);
}``````

Comment hidden because of low score. Click to expand.
0

you can call:

UpdateAncestorMatrix(m, root, 0);

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public class BinaryTreeAncestorMatrix {
private class Node {
int value;
Node left;
Node right;

public Node(int val) {
value = val;
left = null;
right = null;
}
}
Node root = null;

private void createAncestorMatrix(Node currNode, Node parent, int[][] ancestorMatrix, ArrayList<Integer> nodes) {
if(currNode == null) return;
if(currNode != null && parent == null) {
createAncestorMatrix(currNode.left, currNode, ancestorMatrix, nodes);
createAncestorMatrix(currNode.right, currNode, ancestorMatrix, nodes);
}
else {
for(int i = 0 ; i < ancestorMatrix[nodes.indexOf(parent.value)].length; i++)
ancestorMatrix[nodes.indexOf(currNode.value)][i] = ancestorMatrix[nodes.indexOf(parent.value)][i];
ancestorMatrix[nodes.indexOf(currNode.value)][nodes.indexOf(parent.value)] = 1;
createAncestorMatrix(currNode.left, currNode, ancestorMatrix, nodes);
createAncestorMatrix(currNode.right, currNode, ancestorMatrix, nodes);
}
}

createAncestorMatrix(root, null, ancestorMatrix, nodes);

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.