Amazon Interview Question SDE-2s
Team: Kindle
Country: India
Interview Type: Written Test
1. Do level order traversing.
2. if(root==null) return;
else
for each level in the tree
a. maintain a queue. (like BFS)
b. Insert using add(element);
c. for a given level compare first() and count-1() until q.size() for that level., if needed elements can be moved to an auxiliary memory and compared.
d. during pop() operation, the child nodes has to be inserted in the queue.
The side doesn't let me to paste my dotnetfiddle link here, but you can still check it out, the id is /nchavf.
// C# code:
using System;
using System.Collections.Generic;
namespace PracticeProgrammingPack
{
public partial class Program
{
// This method first creates the list of left child nodes by visting them in a VLR fashion,
// Then, creates the list of right child nodes by visting them in a VRL fashion (mirrored),
// Finally compares the 2 above lists to see if they're equal.
// The algorithm runs in O(n)
private static bool IsMirroredBinaryTree(BinaryTree<int> tree)
{
if (tree == null || tree.Root == null)
{
return false;
}
List<int> leftChildren = new List<int>();
List<int> rightChildren = new List<int>();
TraverseLeftVLR(tree.Root.LeftChild, leftChildren);
TraverseRightVRL(tree.Root.RightChild, rightChildren);
if (leftChildren.Count != rightChildren.Count)
{
return false;
}
for (int i = 0; i < leftChildren.Count; i++)
{
if (leftChildren[i] != rightChildren[i])
{
return false;
}
}
return true;
}
// a depth first traverse, in a Visit-Right-Left fashion
private static void TraverseRightVRL(BinaryTreeNode<int> node, List<int> rightChildren)
{
if (node == null)
{
return;
}
rightChildren.Add(node.Value);
TraverseRightVRL(node.RightChild, rightChildren);
TraverseRightVRL(node.LeftChild, rightChildren);
}
// a depth first traverse, in a Visit-Left-Right fashion
private static void TraverseLeftVLR(BinaryTreeNode<int> node, List<int> leftChildren)
{
if (node == null)
{
return;
}
leftChildren.Add(node.Value);
TraverseLeftVLR(node.LeftChild, leftChildren);
TraverseLeftVLR(node.RightChild, leftChildren);
}
public static void Main()
{
// Pardon me for this stupid initialization, but I didn't want to spend time developing a perfect BinaryTree data structure
BinaryTreeNode<int> n1 = new BinaryTreeNode<int> { Value = 60 };
BinaryTreeNode<int> n2 = new BinaryTreeNode<int> { Value = 30 };
BinaryTreeNode<int> n3 = new BinaryTreeNode<int> { Value = 30 };
BinaryTreeNode<int> n4 = new BinaryTreeNode<int> { Value = 20 };
BinaryTreeNode<int> n5 = new BinaryTreeNode<int> { Value = 50 };
BinaryTreeNode<int> n6 = new BinaryTreeNode<int> { Value = 50 };
BinaryTreeNode<int> n7 = new BinaryTreeNode<int> { Value = 20 };
BinaryTreeNode<int> n8 = new BinaryTreeNode<int> { Value = 15 };
BinaryTreeNode<int> n9 = new BinaryTreeNode<int> { Value = 15 };
BinaryTree<int> tree = new BinaryTree<int>();
tree.Root = n1;
tree.Root.LeftChild = n2;
tree.Root.RightChild = n3;
tree.Root.LeftChild.LeftChild = n4;
tree.Root.LeftChild.RightChild = n5;
tree.Root.LeftChild.RightChild.LeftChild = n8;
tree.Root.RightChild.LeftChild = n6;
tree.Root.RightChild.LeftChild.RightChild = n9;
tree.Root.RightChild.RightChild = n7;
Console.WriteLine(IsMirroredBinaryTree(tree));
}
}
public class BinaryTreeNode<T>
{
public T Value { get; set; }
public BinaryTreeNode<T> LeftChild { get; set; }
public BinaryTreeNode<T> RightChild { get; set; }
}
public class BinaryTree<T>
{
public BinaryTreeNode<T> Root { get; set; }
}
}
Your concept is correct, except for the fact that you also need to add "NULL" or any number representing null to the list of children. This is because if you don't add "NULL" then the order of the children will not be proper. For e.g
60
/ \
30 30
\ /
50 50
this will give you "its a mirror" whereas it is "not a mirror".
private static bool AreTreesMirrored(TreeNode n1, TreeNode n2)
{
if (n1 == null && n2 == null)
{
return true;
}
if (n1 == null || n2 == null)
{
return false;
}
return n1.Value == n2.Value &&
AreTreesMirrored(n1.Left, n2.Right) &&
AreTreesMirrored(n1.Right, n2.Left);
}
public static bool IsTreeMirrored(TreeNode n)
{
bool ret = false;
if (n != null)
{
ret = AreTreesMirrored(n.Left, n.Right);
}
return ret;
}
easy to understand
#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node *left,*right;
};
bool is_mirror(node *first_tree,node *second_tree)
{
if(first_tree==NULL && second_tree ==NULL)
return true;
if(first_tree== NULL || second_tree==NULL)
return false;
return (first_tree->data == second_tree->data) &&
is_mirror(first_tree->left,second_tree->right) &&
is_mirror(first_tree->right ,second_tree->left);
}
node *newnode(int d)
{
node * temp=new node;
temp->data=d;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int main()
{
node *first_tree = newnode(1);
first_tree->left = newnode(2);
first_tree->right = newnode(3);
first_tree->left->left = newnode(4);
first_tree->left->right = newnode(5);
first_tree->right->left = newnode(6);
first_tree->right->right = newnode(3);
node *second_tree = newnode(1);
second_tree->left = newnode(3);
second_tree->right = newnode(2);
second_tree->left->left = newnode(7);
second_tree->left->right = newnode(6);
second_tree->right->left = newnode(5);
second_tree->right->right = newnode(4);
is_mirror(first_tree,second_tree)?cout<<"yes"<<endl:cout<<"no"<<endl;
}
private boolean isMirroredTree(Node tree) {
if(tree == null) {
return false;
}
Queue queue = new Queue();
if(tree.left != null) {
if(tree.right == null)
return false;
queue.push(tree.left);
}
if(tree.right != null) {
if(tree.left == null)
return false;
queue.push(tree.right);
}
return isMirroredQueue(queue, 1);
}
private boolean isMirroredQueue(Queue queue, int level) {
if(queue.isEmpty()) {
return true;
}
if(queue.size() != Math.power(2, level)) {
return false;
}
Queue temp = new Queue();
for(int i=0; i<(Math.power(2, level)/2); i++) {
int item = queue.pop();
temp.push(item);
if(item.left != null) {
if(item.right == null)
return false;
queue.push(item.left);
}
if(item.right != null) {
if(item.left == null)
return false;
queue.push(item.right);
}
}
for(int i= Math.power(2, level)/2; i<Math.power(2, level); i++) {
int item = temp.pop();
if(queue.pop() != item)
return false;
if(item.left != null) {
if(item.right == null)
return false;
queue.push(item.left);
}
if(item.right != null) {
if(item.left == null)
return false;
queue.push(item.right);
}
}
return isMirroredQueue(queue, i++);
}
private boolean isMirroredTree(Node tree) {
if(tree == null) {
return false;
}
Queue queue = new Queue();
if(tree.left != null) {
if(tree.right == null)
return false;
queue.push(tree.left);
}
if(tree.right != null) {
if(tree.left == null)
return false;
queue.push(tree.right);
}
return isMirroredQueue(queue, 1);
}
private boolean isMirroredQueue(Queue queue, int level) {
if(queue.isEmpty()) {
return true;
}
if(queue.size() != Math.power(2, level)) {
return false;
}
Queue temp = new Queue();
for(int i=0; i<(Math.power(2, level)/2); i++) {
int item = queue.pop();
temp.push(item);
if(item.left != null) {
if(item.right == null)
return false;
queue.push(item.left);
}
if(item.right != null) {
if(item.left == null)
return false;
queue.push(item.right);
}
}
for(int i= Math.power(2, level)/2; i<Math.power(2, level); i++) {
int item = temp.pop();
if(queue.pop() != item)
return false;
if(item.left != null) {
if(item.right == null)
return false;
queue.push(item.left);
}
if(item.right != null) {
if(item.left == null)
return false;
queue.push(item.right);
}
}
return isMirroredQueue(queue, i++);
}
Using DFS:
bool isMirrored(Node root) {
Queue<int> mirrorQ;
isMirroredPush(root.left, mirrorQ);
return isMirrored(root.right, mirrorQ);
}
void isMirroredPush(Node root, Queue<int> mirrorQ) {
if (root == null) {
mirrorQ.enqueue(-1);
return;
}
mirrorQ.enqueue(root.value);
isMirroredPush(root.left, mirrorQ);
isMIrroredPush(root.right, mirrorQ);
}
bool isMirrored(Node root, Queue<int> mirrorQ) {
if (mirrorQ.size() == 0) {
return false;
}
int val = mirrorQ.dequeue();
if (root == null) {
return val == -1;
}
if (root.value != val) {
return false;
}
return isMirrored(root.right, mirrorQ) && isMirrored(root.left, mirrorQ);
}
Haven't found any solution with a stack yet, so here you go (C#):
static bool CheckMirrored(Node node)
{
var stack = new Stack<int>();
stack.Push(node.Value);
void Push(Node node)
{
if (node == null) return;
if (stack.TryPeek(out var stVal) && stVal == node.Value)
{
stack.Pop();
}
else
{
stack.Push(node.Value);
}
}
void PushChildren(Node node)
{
if (node == null) return;
Push(node.Left);
Push(node.Right);
PushChildren(node.Left);
PushChildren(node.Right);
}
PushChildren(node);
return stack.Count == 1;
}
- dmi March 12, 2017public boolean isMirrored(TreeNode t){ if(t!=null) return isMirrored(t.left,t.right); return false; } public boolean isMirrored(TreeNode a, TreeNode b){ if(a==null && b==null) return true; if(a==null ^ b==null) return false; if(a.data==b.data){ return isMirrored(a.left,b.right) && isMirrored(a.right,b.left); } } /*class TreeNode{ int data; TreeNode left; TreeNode right; }*/