Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Do a level order traversal. Remember for null leaves enter blank in an array
eg
1
2 3
4 6 7
post order traversal is : 1234_67
Now here we follow the property that child will always be at 2i and 2i+1 index or vise versa parent is always at |i/2| index
therefore parent of 1 will be no one
parent of 2 = 2/2 = 1 i.e 1
parent of 3 = 3/2 = 1 i.e 1
parent of 4 = 4/2 = 2 i.e 2 and rest copy from 2
parent of 6 = 6/2 = 3 i.e 3 and rest copy from 3
parent of 7 = 7/2 = 3 i.e 3 and rest copy from 3
The tree is numbered as 1...N so the tree that you have taken as an example will actually be :
--------1
------2---3
----4----5--6
where 2 doesn't have a right child so you're formula will not work here.
To apply your concept you need to change the numbers of each node but then you won't be able to find the right index of that node in the matrix.
Another solution will be to keep another value associated with each node but will cost you Θ(N) space complexity.
Ashish can you please explain how it will not work>
For no right child I am using a blank in the array.
This will work only if tree is balanced, another solution is you can use DFS as you reach node b put Arr[a][b] =1 for all a (nodes present in the stack of DFS)
To find all ancestor relationship, you do an in-order traversal of the tree using recursion, while keeping the current path from the root in a stack by pushing each node we traverse into the stack (and popping it when we are done with it). To find the ancestors of a node, we iterate the items in the stack and mark an ancestor relationship between each item and the current node.
The time complexity is O(Nh) because we iterate all the nodes in the tree which is O(N), and for each node we iterate all its ancestors, which is O(h) - the height of the tree. Since h=O(N) in the worst case (if the tree is single list), then the time is O(N^2), which is optimal because the number of possible ancestor relationships is N^2 (the size of the matrix).
If the tree is balanced then h=O(log N), thus the time complexity is O(N log N).
The space complexity is O(h), which is O(N) for unbalanced tree or O(log N) for a balanced tree.
@gen-y-s: I think what you mean is this right?:
Suppose you have binary tree of this form:
8
6 11
5 7 10 12
We have postorder code as below which is slightly modified:
postorder(node)
if node == null then return
put_in_stack(node)
postorder(node.left)
postorder(node.right)
visit(node)
algorithm:
1.Start doing post order traversal.
2.put all the nodes in the stack as shown above i.e. basically all the paths from root to the current node.
3. Once you reach the node i.e. visit(node) in the above algorithm then just pop the node and do as below:
while(reach from bottom to top of stack) {
element = bottom_of_stack;
matrix[element][popped_node]=1.
bottom_of_stack++
}
code below:
#include<stdlib.h>
#include<stdio.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}
if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
void print_postorder(node * tree)
{
if (tree)
{
printf("stack %d\n", tree->data);
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}
void main()
{
node *root;
node *tmp;
root = NULL;
/* Inserting nodes into tree */
insert(&root, 8);
insert(&root, 6);
insert(&root, 11);
insert(&root, 5);
insert(&root, 7);
insert(&root, 10);
insert(&root, 12);
printf("Post Order Display\n");
print_postorder(root);
}
dry run:
stack 8
stack 6
stack 5
5 {8,5} {6,5} ---> set the matrix and pop 5 from stack.
stack 7
7 {8,7} {6,7} ---> set the matrix and pop 7 from stack.
6 {8,6} ---> set the matrix and pop 6 from stack.
stack 11
stack 10
10 {8,10} {11,10} ---> set the matrix and pop 10 from stack.
stack 12
12 {8,12} {11,12} ---> set the matrix and pop 12 from stack.
11 {8,11} ---> set the matrix and pop 11 from stack.
8 --->pop it off :)
Actually, the tree walk should be in pre-order, since we want to process parents before children.
def ancestors(root, mat):
def ancestors_int(node):
if node==None:
return
for item in stack:
mat[item.val][node.val]=1
stack.append(node)
ancestors_int(node.left)
ancestors_int(node.right)
stack.pop()
stack=[]
ancestors_int(root)
From the definition of Arr[A][B], node A is ancestor of B. So for Arr[i][j] j has i as ancestor and all ancestors of i are also ancestors of j. So for all i in Arr[i][j] copy Arr[k][i] == 1.
Start traversing the binary tree in level order fashion and update ancestors of parent node for the current node as the ancestors of the current node.
A modified preorder traversal will do
Find my code snippets
public class Node {
int value;
Node leftChild;
Node rightChild;
Node parent;
public Node(int nodeVal) {
value = nodeVal;
leftChild = null;
rightChild = null;
parent = null;
}
}
private void modifiedPreOrderTraversal(Node currNode, int[][] ancestorMatrix) {
if(currNode == null) return;
else {
if(currNode.parent != null) {
int currNodePositionInAncestorMatrix = -1;
int parentNodePositionInAncestorMatrix = -1;
for(int i = 0; i < inputNodes.length; i++) {
if(inputNodes[i] == currNode.value) currNodePositionInAncestorMatrix = i;
if(inputNodes[i] == currNode.parent.value) parentNodePositionInAncestorMatrix = i;
}
//Parent Node of Current Node
ancestorMatrix[parentNodePositionInAncestorMatrix][currNodePositionInAncestorMatrix] = 1;
//Ancestor updation of Current Node
for(int i = 0; i < inputNodes.length; i++) {
if(ancestorMatrix[i][parentNodePositionInAncestorMatrix] == 1)
ancestorMatrix[i][currNodePositionInAncestorMatrix] = 1;
}
}
modifiedPreOrderTraversal(currNode.leftChild, ancestorMatrix);
modifiedPreOrderTraversal(currNode.rightChild, ancestorMatrix);
}
}
public int[][] getAncestorMatrix() {
if(head == null) return null;
int[][] ancestorMatrix = new int[inputNodes.length][inputNodes.length];
for(int i = 0; i < inputNodes.length; i++)
for(int j = 0; j < inputNodes.length; j++)
ancestorMatrix[i][j] = 0;
modifiedPreOrderTraversal(head, ancestorMatrix);
return ancestorMatrix;
}
void updateMatrixfromBinaryTree(int Arr[][], int parent[], node)
{
if(node.left == null && node.right == null)
{
//update all the parents of each leaf node to 1
for each(parent p in parent[])
{
a[p][node.data] = 1;
}
return;
}
parent.add(node.data);
updateMatrixfromBinaryTree(Arr[][],parent[],node.leftchild);
updateMatrixfromBinaryTree(Arr[][],parent[],node.rightchild);
}
Question here might resemble to some graph theory.May be Prim's Algo can be implemented here.
First, row first column will have all 0's.
Second row will have 1's to only those who are their ancestor. Now Algo follows the same pattern Subsequently except on one occasion, where if the node parent has marked 1 on its ancestor to some other node, then this node also have to mark 1 for that node .
My solution for this problem. The complexity is O(N*N).
typedef struct Node{
Node *left, *right;
int val, id;
};
void ancestor(Node * parent, Node *node, int **arr, int n) {
if (node == NULL)
return;
int n_id = node->id;
if (parent != NULL) {
int p_id = parent->id;
for (int i = 0; i < n; i++) {
arr[i][n_id] = arr[i][p_id];
}
arr[p_id][n_id] = 1;
}
ancestor(node, node->left, arr, n);
ancestor(node, node->right, arr,n);
}
public void UpdateMatrix(Node node, int[,] matrix)
{
if (node == null)
return;
if (node.Left != null)
{
UpdateMatrix(node.Left, matrix);
for (int i = 0; i < matrix.GetLength(1); i++)
matrix[node.Value - 1, i] = matrix[node.Value - 1, i] | matrix[node.Left.Value - 1, i];
matrix[node.Value - 1, node.Left.Value - 1] = 1;
}
if (node.Right != null)
{
UpdateMatrix(node.Right, matrix);
for (int i = 0; i < matrix.GetLength(1); i++)
matrix[node.Value - 1, i] = matrix[node.Value - 1, i] | matrix[node.Right.Value - 1, i];
matrix[node.Value - 1, node.Right.Value - 1] = 1;
}
}
public static void treeToMatrix(Node node, int[][] a, Stack<Node> s) {
s.push(node);
if (node.getLeft() != null) {
treeToMatrix(node.getLeft(), a, s);
Node c = s.pop();
for (Node n : s) {
a[n.getValue()][c.getValue()] = 1;
}
}
if (node.getRight() != null) {
treeToMatrix(node.getRight(), a, s);
Node c = s.pop();
for (Node n : s) {
a[n.getValue()][c.getValue()] = 1;
}
}
}
public static List<Node> list=new List<Node>();
public static int[,] matrix=new int[n,n];
public static void Matrix(Node root,)
{
if(root==null)
return;
list.Add(root);
Matrix(root.Left);
Matrix(root.Right);
list.Remove(list[list.count-1]);
for(int i=0;i<list.count;++i)
{
matrix[list[i].ID,root.ID]=1;
}
}
struct TreeNode
{
TreeNode* left;
TreeNode* right;
bool visited;
int id;
};
struct DFSNode
{
TreeNode* node;
DFSNode* next;
DFSNode* prev;
};
void MarkAncestors(TreeNode* root, int Arr[][])
{
DFSNode* visitStack = new DFSNode();
visitStack->node = root;
DFSNode* top = visitStack;
while(top != NULL)
{
TreeNode* tn = top->node;
if(tn->left && !tn->left->visited)
{
tn->left->visited = true;
DFSNode* newChild = new DFSNode();
newChild->node = tn->left;
Arr[tn->id][tn->left->id] = 1;
top->next = newChild;
newChild->prev = top;
top = newChild;
}
else if(tn->right && !tn->right->visited)
{
tn->right->visited = true;
DFSNode* newChild = new DFSNode();
newChild->node = tn->right;
Arr[tn->id][tn->right->id] = 1;
top->next = newChild;
newChild->prev = top;
top = newChild;
}
else
{
DFSNode* old = top;
top = top->prev;
if(top != NULL)
{
top->next = NULL;
}
delete old;
}
}
}
arr[i][j]=1 if i is parent of j
arr[i][j]=1 if arr[i][parent of j]=1 i.e. i is ancestor of j if it is ancestor or parent of (parent of j)
else it remains zero...
and traverse the tree in level order traversal....
if the numbers are in increasing order from root to bottom in left to right fashion then no need for level order traversal...
- Putta May 27, 2013int a[n][n] = 0; setArray(std::vector<int> arr, node) { if(node == NULL) return; arr.push_back(node->val); setArray(arr, node->left); setArray(arr, node->right); arr.pop_back(); for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it) a[*it][node->val] = 1; }