Amazon Interview Question for SDE-2s


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

- divm01986 October 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zaitcev.anton October 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Shivam Maharshi October 26, 2015 | Flag
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;
}

- Anonymous October 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- teli.vaibhav October 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anonymous October 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- teli.vaibhav October 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ragmo2223 November 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ragmo2223 November 03, 2015 | Flag
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;
}

- kyduke October 02, 2015 | Flag Reply
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)

- teli.vaibhav October 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
			map.Add(root.data, false);
		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;
	}
}

- codealtecdown October 02, 2015 | Flag
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);
}

- oelsayed October 02, 2015 | Flag Reply
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.

- Anonymous October 03, 2015 | Flag Reply
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) {
        setValues.add(parent.getValue());
        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>());
            }
            parent.getChildren().add(n);

            // 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) {
                        newParents.addAll(child.getChildren());
                    }
                    // 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

- Mger October 03, 2015 | Flag Reply
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) {
        setValues.add(parent.getValue());
        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>());
            }
            parent.getChildren().add(n);

            // 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) {
                        newParents.addAll(child.getChildren());
                    }
                    // 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

- Mger October 03, 2015 | Flag Reply
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) {
        setValues.add(parent.getValue());
        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>());
            }
            parent.getChildren().add(n);

            // 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) {
                        newParents.addAll(child.getChildren());
                    }
                    // 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;
        }

    }
}

- mger1979 October 03, 2015 | Flag Reply
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.

- assaf October 03, 2015 | Flag Reply
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.

- Bharath October 06, 2015 | Flag Reply
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.

- Bharath October 06, 2015 | Flag Reply
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.

- Anonymous October 09, 2015 | Flag Reply
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;
        addMap(nodeMap, node->leftNode);
        addMap(nodeMap, node->rightNode);
    }
}

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};
    
    addMap(&nodeMap, firstBinaryTree);
    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;
    }
}

- Hsien Chang Peng October 09, 2015 | Flag Reply
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);
}

- peter tang October 23, 2015 | Flag Reply
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;
}

- PoWerOnOff November 17, 2015 | Flag Reply
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))
        values.Add(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);
        matched.Add(node.Value);
    }

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

- hnatsu March 26, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More