Amazon Interview Question
SDE1sTeam: Kindle
Country: India
Interview Type: Written Test
Recursive approach:
private static boolean isFoldable(BinaryTree t1, BinaryTree t2) {
if (t1 == null && t2 == null)
return true;
if (t1 == null || t2 == null)
return false;
if (t1.getData() != t2.getData())
return false;
return isFoldable(t1.getLeft(), t2.getRight()) && isFoldable(t1.getRight(), t2.getLeft());
}
Following is a non-recursive approach :
#define TRUE 1
#define FALSE 0
int isFoldable(Node * head){
char [] leftSequence = left_to_right_preorder(head->left_child);
char [] rightSequence = right_to_left_preorder(head->right_child);
if(is_equal(leftSequence, rightSequence)){
return TRUE;
}
return FALSE;
}
char[] left_to_right_preorder(Node * node){
Queue queue;
enqueue_left_to_right_in_queue(&queue, node);
char result[queue.size() + 1];
result[0] = queue.size();
for(int i = 1;i <= queue.size(); i++){
result[i] = queue.pop().value;
}
return result;
}
void enqueue_left_to_right_in_queue(Queue * queue, Node * node){
if(node != null){
queue.push(node);
enqueue_left_to_right_in_queue(queue, node->left);
enqueue_left_to_right_in_queue(queue, node->right);
}
}
char[] right_to_left_preorder(Node * node){
Queue queue;
enqueue_right_to_left_in_queue(&queue, node);
char result[queue.size()+ 1] ;
result[0] = queue.size();
for(int i = 1 ; i <= queue.size(); i++){
result[i] = queue.pop().value;
}
return result;
}
void enqueue_right_to_left_in_queue(Queue * queue, Node * node){
if(node != null){
queue.push(queue, node);
enqueue_right_to_left_in_queue(queue, node->right_child);
enqueue_right_to_left_in_queue(queue, node->left_child);
}
}
int is_equal(char* first, char* second){
if(first[0] != second[0]){
return 0;
}
for(int i = 1; i <= first[0]; i++){
if(first[i] != second[i]){
return 0;
}
}
return 1;
}
How about this:
1. Say root is R.
2. do an in-order traversal and keep putting element in a stack (say stack1) till we reach R to be put in stack1 (i.e. we processed all element in left sub tree).
3. Pop R.
4. Now we would go to right sub tree of R.
5. Process an element E in in-order traversal,
6. POP from stack1.
if (stack empty)
return false
else if (popped element = E)
goto 5.
else
return false;
7. if (stack empty)
return true;
else
return false;
How about this:
1. Say root is R.
2. do an in-order traversal and keep putting element in a stack (say stack1) till we reach R to be put in stack1 (i.e. we processed all element in left sub tree).
3. Pop R.
4. Now we would go to right sub tree of R.
5. Process an element E in in-order traversal,
6. POP from stack1.
if (stack empty)
return false
else if (popped element = E)
goto 5.
else
return false;
7. if (stack empty)
return true;
else
return false;
How about this:
1. Say root is R.
2. do an in-order traversal and keep putting element in a stack (say stack1) till we reach R to be put in stack1 (i.e. we processed all element in left sub tree).
3. Pop R.
4. Now we would go to right sub tree of R.
5. Process an element E in in-order traversal,
6. POP from stack1.
if (stack empty)
return false
else if (popped element = E)
goto 5.
else
return false;
7. if (stack empty)
return true;
else
return false;
Define a Method IsMirror(Tree t1, Tree t2);
Now problem is just to call this method appropriately
bool IsFoldable(Tree t)
{
if (t == null) return true;
return IsMirror(t.Left, t.Right);
}
bool IsMirror(Tree t1, Tree t2)
{
if (t1 == null && t2 == null)
{
return true;
}
if (t1 == null || t2 == null)
{
return false;
}
if (t.data != t2.data)
{
return false;
}
return IsMirror(t1.right, t2.left) && (t1.left. t2.right);
}
non-recursive way
bool isMirrorTree (treeNode * root)
{
std::queue<treeNode *> treeQ;
bool isMirror = true;
if (root->l == NULL && root->r ==NULL)
return true;
if ((root->l == NULL && root->r !=NULL) ||
(root->l != NULL && root->r == NULL))
return false;
treeQ.push (root->l);
treeQ.push (root->r);
while (! treeQ.empty()) {
treeNode *first = treeQ.front ();
treeQ.pop ();
treeNode *second= treeQ.front ();
treeQ.pop ();
if ( first && second && first->x == second->x)
{
treeQ.push (first->l);
treeQ.push (second->r);
treeQ.push (first->r);
treeQ.push (second->l);
}
else
{
if (! (first == NULL && second == NULL))
isMirror =false;
break;
}
}
return isMirror;
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isMirror(TreeNode* root) {
if(root->right->val==root->left->val)
{
return isEqual(root->left->left,root->right->right)&&isEqual(root->left->right,root->right->left);
}
else return false;
}
bool isEqual(TreeNode* root1,TreeNode* root2) {
if(root1->val==root2->val)
{
return isEqual(root1->left,root2->left)&&isEqual(root1->right,root2->right);
}
else return false;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isMirror(TreeNode* root) {
if(root->right->val==root->left->val)
{
return isEqual(root->left->left,root->right->right)&&isEqual(root->left->right,root->right->left);
}
else return false;
}
bool isEqual(TreeNode* root1,TreeNode* root2) {
if(root1->val==root2->val)
{
return isEqual(root1->left,root2->left)&&isEqual(root1->right,root2->right);
}
else return false;
}
};
- Vir Pratap Uttam May 10, 2015