## Amazon Interview Question

**Country:**India

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.

@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

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);

}

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);
}
}
```

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);
}
```

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);
}
}
```

```
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);
}
```

```
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) {
nodes.add(currNode.value);
createAncestorMatrix(currNode.left, currNode, ancestorMatrix, nodes);
createAncestorMatrix(currNode.right, currNode, ancestorMatrix, nodes);
}
else {
nodes.add(currNode.value);
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);
}
```

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

The time complexity is O(n).

- oOZz June 17, 2013