## Amazon Interview Question for SDE-2s

• 0

Country: United States
Interview Type: Phone Interview

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

``````public class Node
{
int value;
Node left;
Node right;
}

public class BinaryTreeSvc
{
public boolean hasSameValues(Node a,Node b) throws NullPointerException
{
if(a==null||b==null)
{
throw new NullPointerException();
}

HashMap<Integer,Boolean> values=new HashMap<Integer,Boolean>();
fillMap(a,values);

//Check if all of the values in the hash map are present in the second tree.
return values.isEmpty();

}

public void fillMap(Node n,HashMap<Integer,Boolean> mp)
{
if(n==null)
{
return;
}
mp.put(n.value,true);
fillMap(n.left,mp);
fillMap(n.right,mp);
}

private void checkMap(HashMap<Integer,Boolean> mp,Node s)
{
if(s==null)
{
return;
}
if(mp.containsKey(s.value()))
{
mp.remove(s.value());
}
checkMap(mp,s.left);
checkMap(mp,s.right);
}
}
//Time complexity: O(n), Space complexity O(n).``````

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

why do you need to call "containsKey" before "remove" ?

"remove" returns null if key is NOT found in map - in such case, you should return "false" and stop checking

I would also use HashSet instead HashMap

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

I like the overall approach however this will not work in the case where the Second Set is bigger than the First set take this case for example:

First Set:- 1,2,3,4,5
Second Set:- 1,2,3,4,5,6,7,8

Fill map will put all entries from 1-5 into map, and check map will remove all of them from map but 7 and 8 were not present, so ideally it should return false but your program will return true.

Solution:-
When you find some entry not present, return false immediately.

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

Convert BST to set. And compare 2 sets.
c++, brute force

``````void makeIntegerArray(Node* node, set<int>& arr) {
if (node == NULL) return;
arr.insert(node->value);
makeIntegerArray(node->left, arr);
makeIntegerArray(node->right, arr);
}

bool haveSameIntegers(Node* a, Node* b) {
set<int> arrA, arrB;
set<int>::iterator itA, itB;

makeIntegerArray(a, arrA);
makeIntegerArray(b, arrB);

if (arrA.size() != arrB.size()) return false;

itA = arrA.begin();
itB = arrB.begin();
while (itA != arrA.end() && itB != arrB.end()) {
if (*itA != *itB) return false;
itA++;
itB++;
}

return true;
}``````

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

It is not a BST, its only a BT. The above solution would work correctly for a BST only if you had done an Indorder traversal instead of a preorder because it looks like you are expecting both arrays to be sorted.

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

@teli.vaibhav, you just need to traverse the tree and add to the set, doesn't matter if it's a BST or not.
If the two sets are identical, then return true, otherwise return false. Simple.

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

Well.. the Sets sure should have same identical integers.
But I don't see you comparing the Sets, you converted the 2 sets into 2 arrays and compared the 2 arrays element by element sequentially.. It will fail there as the integers in both arrays though the same, wouldn't be the same sequentially.

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

@telo.vaibhav - he NAMED the set "arr", he did not actually convert them to arrays. He chose a bad name for variables is all.

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

But it's still not right. Iterating through the set's will have similar behavior as arrays

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

Convert BT to set. Compare 2 sets.
c++, brute force

``````void makeIntegerArray(Node* node, set<int>& arr) {
if (node == NULL) return;
arr.insert(node->value);
makeIntegerArray(node->left, arr);
makeIntegerArray(node->right, arr);
}

bool haveSameIntegers(Node* a, Node* b) {
set<int> arrA, arrB;
set<int>::iterator itA, itB;

makeIntegerArray(a, arrA);
makeIntegerArray(b, arrB);

if (arrA.size() != arrB.size()) return false;

itA = arrA.begin();
itB = arrB.begin();
while (itA != arrA.end() && itB != arrB.end()) {
if (*itA != *itB) return false;
itA++;
itB++;
}

return true;
}``````

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

Step 1: Do a simple Inorder traversal of the first tree & save each integer in a Map1<Integer value, number of occurrences>

Step 3: Do a simple Inorder traversal of the second tree & save each integer in Map2, also, check whether each integer is present in the Map1 or not.

If not present, we return false right away.
If present, if the number of occurrences is only 1 (value in Map1), we delete the element else we simply decrement the count.

Step 4:
If your Map1 is empty, it means all the elements are present, return true.

If Map1 is not empty, validate the remaining elements are present in Map2. If yes, return true, else false.

Time complexity: O(m+n)
Space Complexity: O(m+n)

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

c# implementation using Dictionary. Please check and comment.

``````using System;
using System.Collections.Generic;

public class Test
{
public static void Main()
{
Node root1 = new Node(5);
root1.left = new Node(1);
root1.right = new Node(6);
root1.left.left = new Node(5);
root1.left.right = new Node(4);
root1.right.left = new Node(3);
root1.right.right = new Node(6);

Node root2 = new Node(1);
root2.left = new Node(3);
root2.right = new Node(4);
root2.left.left = new Node(6);
root2.left.right = new Node(5);

if(HaveSameData(root1,root2))
Console.WriteLine("Same Data");
else
Console.WriteLine("Not same Data");
}

static bool HaveSameData(Node root1, Node root2)
{
Dictionary<int,bool> map = new Dictionary<int,bool>();

Traverse(root1, map);
if(!TraverseAndCheck(root2, map))
return false;

foreach(KeyValuePair<int,bool> item in map)
{
if(!item.Value)
return false;
}

return true;
}

static void Traverse(Node root, Dictionary<int,bool> map)
{
if(root == null)
return;

Traverse(root.left, map);
if(map.ContainsKey(root.data))
map[root.data] = false;
else
Traverse(root.right, map);
}

static bool TraverseAndCheck(Node root, Dictionary<int,bool> map)
{
if(root == null)
return true;

if(map.ContainsKey(root.data))
map[root.data] = true;
else
return false;
return TraverseAndCheck(root.right, map) && TraverseAndCheck(root.left, map);
}

}

public class Node
{
public int data;
public Node left;
public Node right;
public Node(int d)
{
data = d;
}
}``````

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

``````function tree_equals(\$root1, \$root2){
if((\$root1 && !\$root2) || (\$root2 && !\$root1)){
return FALSE;
}
if(\$root1->data != \$root2->data){
return FALSE;
}
if((!\$root1 && !\$root2){
return TRUE;
}

return tree_equals(\$root1->left, \$root2->left) && tree_equals(\$root1->right, \$root2->right);
}``````

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

1. Take temp array and initialize all elements to -1.
2. Now traversere tree1 and mark all position of all visited elements in array to 1. if number is repeated keep it same as 1.
3. Now traverse tree2 and for all elements decrease the array counter.
4. If array has any of the element to be 1 then both trees has same integers.

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

In java it is very simple.
The following code demonstrating 3 ways of doing this with time comparison

``````import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class TestBT {

public static void main(String[] args) {
// filling trees
Integer[] valuesA = new Integer[100000];
for (int i = 0; i < 100000; i++) {
valuesA[i] = i;
}
Integer[] valuesB = new Integer[100000];
for (int i = 99999; i >= 0; i--) {
valuesB[i] = i;
}

Node rootA = fillAsBinaryTreeUseFlatData(valuesA);
Node rootB = fillAsBinaryTreeUseFlatData(valuesB);

final int MAX_CIRCLE = 100;
long start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsTreeSet(rootA, rootB);
}
System.out.println("checkAsTreeSet: " + (new Date().getTime() - start));

start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkSimple(rootA, rootB);
}
System.out.println("checkSimple: " + (new Date().getTime() - start));

start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsMixedSet(rootA, rootB);
}
System.out.println("checkAsMixedSet: " + (new Date().getTime() - start));

if (checkAsMixedSet(rootA, rootB)) {
System.out.println("the same");
} else {
System.out.println("not the same");
}

}

public static boolean checkSimple(Node rootA, Node rootB) {
// starting to compare
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();

recursive(rootA, setA);
recursive(rootB, setB);

// yes Set will compare collections, but if this is uncomfortable
// for you then you can use alternative way setA.containsAll(setB)
return setA.equals(setB);

}

public static boolean checkAsTreeSet(Node rootA, Node rootB) {
// starting to compare
TreeSet<Integer> setA = new TreeSet<Integer>();
TreeSet<Integer> setB = new TreeSet<Integer>();

recursive(rootA, setA);
recursive(rootB, setB);

if (setA.size() == setB.size()) {
Iterator<Integer> iterA = setA.iterator();
Iterator<Integer> iterB = setB.iterator();
while (iterA.hasNext()) {
if (iterA.next() != iterB.next()) {
return false;
}
}
}
return true;
}

public static boolean checkAsMixedSet(Node rootA, Node rootB) {
// the best way is to make set of the smallest tree first, but it is fast even without this
HashSet<Integer> setA = new HashSet<Integer>();
// make set of first Tree
recursive(rootA, setA);
//check all nodes from second tree whether they are in setA
return recursiveSetCheck(rootB, setA);
}

public static void recursive(Node parent, Set<Integer> setValues) {
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
recursive(child, setValues);
}
}
}

public static boolean recursiveSetCheck(Node parent, Set<Integer> setValues) {
// if current node value is not in set we can stop recursion and exit
if (!setValues.contains(parent.getValue())) {
return false;
}
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
if (!recursiveSetCheck(child, setValues)) {
return false;
}
}
}
return true;
}

/**
* Method for filling tree as binary tree
*
* @param values
*            - sequence of integer values of binary tree should be as node
*            sequences root, 1L,1R,2LL,2LR,2RL,2LL,3LLL,3LLR,3LRL,3LRR...
*/
public static Node fillAsBinaryTreeUseFlatData(Integer... values) {

int parentIndex = 0;// index of current parent node
Node root = new Node(values[0]); // root node
Node[] parents = new Node[] { root }; // all current parents
for (int i = 1; i < values.length; i++) {
// getting current node and his parent
Node n = new Node(values[i]);
Node parent = parents[parentIndex];

if (parent.getChildren() == null) {
parent.setChildren(new ArrayList<Node>());
}

// if current parent already has two children, we should take
// another sibling
if (parent.getChildren().size() == 2) {
if (parentIndex + 1 >= parents.length) {
// if there is no other sibling we should make all children
// of current parents as parents for the next level nodes
parentIndex = 0;
List<Node> newParents = new ArrayList<Node>();
for (Node child : parents) {
}
// now all previous level nodes become a parents
parents = newParents.toArray(new Node[newParents.size()]);
} else {
// taking another sibling
parentIndex++;
}
}
}
return root;
}

public static class Node {
private Integer value;
private List<Node> children;

public Node(Integer value) {
this.value = value;
}

public Integer getValue() {
return value;
}

public void setValue(Integer value) {
this.value = value;
}

public List<Node> getChildren() {
return children;
}

public void setChildren(List<Node> children) {
this.children = children;
}

}
}``````

On my PC the output was:
checkAsTreeSet: 3233
checkSimple: 2439
checkAsMixedSet: 1284
the same

So the checkAsMixedSet is faster then all others

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

In java it is very simple.
The following code demonstrating 3 ways of doing this with time comparison

``````import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class TestBT {

public static void main(String[] args) {
// filling trees
Integer[] valuesA = new Integer[100000];
for (int i = 0; i < 100000; i++) {
valuesA[i] = i;
}
Integer[] valuesB = new Integer[100000];
for (int i = 99999; i >= 0; i--) {
valuesB[i] = i;
}

Node rootA = fillAsBinaryTreeUseFlatData(valuesA);
Node rootB = fillAsBinaryTreeUseFlatData(valuesB);

final int MAX_CIRCLE = 100;
long start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsTreeSet(rootA, rootB);
}
System.out.println("checkAsTreeSet: " + (new Date().getTime() - start));

start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkSimple(rootA, rootB);
}
System.out.println("checkSimple: " + (new Date().getTime() - start));

start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsMixedSet(rootA, rootB);
}
System.out.println("checkAsMixedSet: " + (new Date().getTime() - start));

if (checkAsMixedSet(rootA, rootB)) {
System.out.println("the same");
} else {
System.out.println("not the same");
}

}

public static boolean checkSimple(Node rootA, Node rootB) {
// starting to compare
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();

recursive(rootA, setA);
recursive(rootB, setB);

// yes Set will compare collections, but if this is uncomfortable
// for you then you can use alternative way setA.containsAll(setB)
return setA.equals(setB);

}

public static boolean checkAsTreeSet(Node rootA, Node rootB) {
// starting to compare
TreeSet<Integer> setA = new TreeSet<Integer>();
TreeSet<Integer> setB = new TreeSet<Integer>();

recursive(rootA, setA);
recursive(rootB, setB);

if (setA.size() == setB.size()) {
Iterator<Integer> iterA = setA.iterator();
Iterator<Integer> iterB = setB.iterator();
while (iterA.hasNext()) {
if (iterA.next() != iterB.next()) {
return false;
}
}
}
return true;
}

public static boolean checkAsMixedSet(Node rootA, Node rootB) {
// the best way is to make set of the smallest tree first, but it is fast even without this
HashSet<Integer> setA = new HashSet<Integer>();
// make set of first Tree
recursive(rootA, setA);
//check all nodes from second tree whether they are in setA
return recursiveSetCheck(rootB, setA);
}

public static void recursive(Node parent, Set<Integer> setValues) {
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
recursive(child, setValues);
}
}
}

public static boolean recursiveSetCheck(Node parent, Set<Integer> setValues) {
// if current node value is not in set we can stop recursion and exit
if (!setValues.contains(parent.getValue())) {
return false;
}
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
if (!recursiveSetCheck(child, setValues)) {
return false;
}
}
}
return true;
}

/**
* Method for filling tree as binary tree
*
* @param values
*            - sequence of integer values of binary tree should be as node
*            sequences root, 1L,1R,2LL,2LR,2RL,2LL,3LLL,3LLR,3LRL,3LRR...
*/
public static Node fillAsBinaryTreeUseFlatData(Integer... values) {

int parentIndex = 0;// index of current parent node
Node root = new Node(values[0]); // root node
Node[] parents = new Node[] { root }; // all current parents
for (int i = 1; i < values.length; i++) {
// getting current node and his parent
Node n = new Node(values[i]);
Node parent = parents[parentIndex];

if (parent.getChildren() == null) {
parent.setChildren(new ArrayList<Node>());
}

// if current parent already has two children, we should take
// another sibling
if (parent.getChildren().size() == 2) {
if (parentIndex + 1 >= parents.length) {
// if there is no other sibling we should make all children
// of current parents as parents for the next level nodes
parentIndex = 0;
List<Node> newParents = new ArrayList<Node>();
for (Node child : parents) {
}
// now all previous level nodes become a parents
parents = newParents.toArray(new Node[newParents.size()]);
} else {
// taking another sibling
parentIndex++;
}
}
}
return root;
}

public static class Node {
private Integer value;
private List<Node> children;

public Node(Integer value) {
this.value = value;
}

public Integer getValue() {
return value;
}

public void setValue(Integer value) {
this.value = value;
}

public List<Node> getChildren() {
return children;
}

public void setChildren(List<Node> children) {
this.children = children;
}

}
}``````

On my PC the output was:
checkAsTreeSet: 3233
checkSimple: 2439
checkAsMixedSet: 1284
the same

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

In java it is very simple.
The following code demonstrating 3 ways of doing this with time comparison

``````package TEST;

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class TestBT {

public static void main(String[] args) {
// filling trees
Integer[] valuesA = new Integer[100000];
for (int i = 0; i < 100000; i++) {
valuesA[i] = i;
}
Integer[] valuesB = new Integer[100000];
for (int i = 99999; i >= 0; i--) {
valuesB[i] = i;
}

Node rootA = fillAsBinaryTreeUseFlatData(valuesA);
Node rootB = fillAsBinaryTreeUseFlatData(valuesB);

final int MAX_CIRCLE = 100;
long start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsTreeSet(rootA, rootB);
}
System.out.println("checkAsTreeSet: " + (new Date().getTime() - start));

start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkSimple(rootA, rootB);
}
System.out.println("checkSimple: " + (new Date().getTime() - start));

start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsMixedSet(rootA, rootB);
}
System.out.println("checkAsMixedSet: " + (new Date().getTime() - start));

if (checkAsMixedSet(rootA, rootB)) {
System.out.println("the same");
} else {
System.out.println("not the same");
}

}

public static boolean checkSimple(Node rootA, Node rootB) {
// starting to compare
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();

recursive(rootA, setA);
recursive(rootB, setB);

// yes Set will compare collections, but if this is uncomfortable
// for you then you can use alternative way setA.containsAll(setB)
return setA.equals(setB);

}

public static boolean checkAsTreeSet(Node rootA, Node rootB) {
// starting to compare
TreeSet<Integer> setA = new TreeSet<Integer>();
TreeSet<Integer> setB = new TreeSet<Integer>();

recursive(rootA, setA);
recursive(rootB, setB);

if (setA.size() == setB.size()) {
Iterator<Integer> iterA = setA.iterator();
Iterator<Integer> iterB = setB.iterator();
while (iterA.hasNext()) {
if (iterA.next() != iterB.next()) {
return false;
}
}
}
return true;
}

public static boolean checkAsMixedSet(Node rootA, Node rootB) {
// the best way is to make set of the smallest tree first, but it is fast even without this
HashSet<Integer> setA = new HashSet<Integer>();
// make set of first Tree
recursive(rootA, setA);
//check all nodes from second tree whether they are in setA
return recursiveSetCheck(rootB, setA);
}

public static void recursive(Node parent, Set<Integer> setValues) {
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
recursive(child, setValues);
}
}
}

public static boolean recursiveSetCheck(Node parent, Set<Integer> setValues) {
// if current node value is not in set we can stop recursion and exit
if (!setValues.contains(parent.getValue())) {
return false;
}
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
if (!recursiveSetCheck(child, setValues)) {
return false;
}
}
}
return true;
}

/**
* Method for filling tree as binary tree
*
* @param values
*            - sequence of integer values of binary tree should be as node
*            sequences root, 1L,1R,2LL,2LR,2RL,2LL,3LLL,3LLR,3LRL,3LRR...
*/
public static Node fillAsBinaryTreeUseFlatData(Integer... values) {

int parentIndex = 0;// index of current parent node
Node root = new Node(values[0]); // root node
Node[] parents = new Node[] { root }; // all current parents
for (int i = 1; i < values.length; i++) {
// getting current node and his parent
Node n = new Node(values[i]);
Node parent = parents[parentIndex];

if (parent.getChildren() == null) {
parent.setChildren(new ArrayList<Node>());
}

// if current parent already has two children, we should take
// another sibling
if (parent.getChildren().size() == 2) {
if (parentIndex + 1 >= parents.length) {
// if there is no other sibling we should make all children
// of current parents as parents for the next level nodes
parentIndex = 0;
List<Node> newParents = new ArrayList<Node>();
for (Node child : parents) {
}
// now all previous level nodes become a parents
parents = newParents.toArray(new Node[newParents.size()]);
} else {
// taking another sibling
parentIndex++;
}
}
}
return root;
}

public static class Node {
private Integer value;
private List<Node> children;

public Node(Integer value) {
this.value = value;
}

public Integer getValue() {
return value;
}

public void setValue(Integer value) {
this.value = value;
}

public List<Node> getChildren() {
return children;
}

public void setChildren(List<Node> children) {
this.children = children;
}

}
}``````

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

I would sort and than compare. the two arrays using 2 pointers.
overall time complexity: O(nlogn).
nlogn for sorting and another pass in T(n) for comparing arrays.

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

A simple C algorithm:
Do any order traversal. For simplicity, i will take inorder traversal. Add the elements into an array. log(n)
Do the same for other tree. Time complexity: log(n)
Sort 2 array: 2*n*log(n)
Compare 2 array; ignore repeated elements.

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

A simple C algorithm:
Do any order traversal. For simplicity, i will take inorder traversal. Add the elements into an array. log(n)
Do the same for other tree. Time complexity: log(n)
Sort 2 array: 2*n*log(n)
Compare 2 array; ignore repeated elements.

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

This can also be done in following way:
1. make inorder traversal on first tree and insert the element in a set.

2. now make traversal in 2nd tree and insert the element in same set. it will detect the presence of common element.

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

``````#include <iostream>
#include <map>

struct Node {
int value;
Node * leftNode;
Node * rightNode;
};

void addMap(std::map<int, bool> * nodeMap, Node * node) {
if (node != nullptr) {
(*nodeMap)[node->value] = true;
}
}

bool checkRepetitiveNumber(std::map<int, bool> * nodeMap, Node * node) {
if (node != nullptr) {
auto search = nodeMap->find(node->value);

if (search == nodeMap->end()) {
return false || checkRepetitiveNumber(nodeMap, node->leftNode) || checkRepetitiveNumber(nodeMap, node->rightNode);
} else {
return true;
}
} else {
return false;
}
}

int main(int argc, const char * argv[]) {
bool                isRepetitive;
Node                * firstBinaryTree, * secondBinaryTree;
std::map<int, bool> nodeMap;

isRepetitive                            = false;

firstBinaryTree                         = new Node{5, nullptr, nullptr};
firstBinaryTree->leftNode               = new Node{1, nullptr, nullptr};
firstBinaryTree->rightNode              = new Node{6, nullptr, nullptr};
firstBinaryTree->leftNode->leftNode     = new Node{5, nullptr, nullptr};
firstBinaryTree->leftNode->rightNode    = new Node{4, nullptr, nullptr};
firstBinaryTree->rightNode->leftNode    = new Node{3, nullptr, nullptr};
firstBinaryTree->rightNode->rightNode   = new Node{6, nullptr, nullptr};

secondBinaryTree                        = new Node{12, nullptr, nullptr};
secondBinaryTree->leftNode              = new Node{33, nullptr, nullptr};
secondBinaryTree->rightNode             = new Node{44, nullptr, nullptr};
secondBinaryTree->leftNode->leftNode    = new Node{64, nullptr, nullptr};
secondBinaryTree->leftNode->rightNode   = new Node{5, nullptr, nullptr};

isRepetitive = checkRepetitiveNumber(&nodeMap, secondBinaryTree);
if (isRepetitive == true) {
std::cout << "There is a repetitive number." << std::endl;
} else {
std::cout << "There isn't a repetitive number." << std::endl;
}
}``````

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

The idea is quite simple that it is to use hash table to take all the elements from the first tree and then check if the second tree has exactly same elements as in the hash table. There is no special about the algorithm but I am going to demonstrate how to use recursive (in some sort of function programming sense) functions to implement the solution. Because tree structure is a very good source to understand functional programming particularly in the sense of sub-problem.
Implementation refer to cpluspluslearning-petert.blogspot.co.uk/2015/10/bts-detect-if-two-tree-have-same.html

TEST

``````void TestCasesOfCheckTwoTreesWithSameElements()
{
const std::vector<int> testInput1 = { 1, 3, 5, 7, 2, 4, 6, 8 };
auto tree1 = ConstructTreeRecursive(testInput1);
assert(tree1 != nullptr);

{
TreeNode<int>* invalid1 = nullptr;
TreeNode<int>* invalid2 = nullptr;

assert(CheckTwoTreesWithSameValues(invalid1, invalid2) == true);
assert(CheckTwoTreesWithSameValues(tree1, invalid2) == false);
assert(CheckTwoTreesWithSameValues(invalid1, tree1) == false);
}

{
const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 1, 5, 2, 4 };
auto tree2 = ConstructTreeRecursive(testInput2);
assert(tree2 != nullptr);
assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
DeleteTree(&tree2);
}

{
const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8 };
auto tree2 = ConstructTreeRecursive(testInput2);
assert(tree2 != nullptr);
assert(CheckTwoTreesWithSameValues(tree1, tree2) == true);
DeleteTree(&tree2);
}

{
const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8, 9 };
auto tree2 = ConstructTreeRecursive(testInput2);
assert(tree2 != nullptr);
assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
DeleteTree(&tree2);
}

DeleteTree(&tree1);
}``````

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

1. Traverse two trees and push numbers in hash set. Duplicated numbers are removed in hash set
2. Compare two hash sets: compare (1) their sizes; (2) numbers one by one.

``````void preorder(TreeNode *root, unordered_set<int> & set){

if(root == NULL)
return;

set.insert(root->val);

preorder(root->left, set);
preorder(root->right, set);
}

bool isIdentical(TreeNode *n1, TreeNode *n2){

unordered_set<int> set1, set2;

preorder(n1, set1);
preorder(n2, set2);

if(set1.size() != set2.size()){
return false;
}

for(unordered_set<int>::iterator it = set1.begin(); it != set1.end(); it++){
if(set2.find(*it) == set2.end()){
return false;		// tree2 does not have a number in tree1
}
}

return true;
}``````

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

``````public bool ContainsSameValues(TreeNode root1, TreeNode root2)
{
var values = GetValues(root1);
return HasSameValues(root2, values);
}

private HashSet<int> GetValues(TreeNode root)
{
var values = new HashSet<int>();
GetValues(root, values);
return values;
}

private void GetValues(TreeNode node, HashSet<int> values)
{
if (node == null)
return;

if (!values.Contains(node.Value))

GetValues(node.Left, values);
GetValues(node.Right, values);
}

private bool HasSameValues(TreeNode root, HashSet<int> values)
{
var matched = new HashSet<int>();
return HasSameValues(root, values, matched) && values.Count == 0;
}

private bool HasSameValues(TreeNode node, HashSet<int> values, HashSet<int> matched)
{
if (node == null)
return true;

if (!matched.Contains(node.Value))
{
if (!values.Contains(node.Value))
return false;

values.Remove(node.Value);
}

return HasSameValues(node.Left, values, matched) && HasSameValues(node.Right, values, matched);
}``````

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.