Google Interview Question

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 9 vote

I propose the following: (i) Perform a DFS to search the tree until we find a candidate node, such that candidate.data == roota.data. (ii) Recursivelly check if A superimpose a subtree with root candidate.

If recursion is unfeasible due to the tree depth (stack overflow) use a DFS via stack and while loop.

A sample code with recursion is shown below:

``````public boolean isSubset(Node a, Node b) {
if ( a== null || b == null)		return false;
if (a.data == b.data)	        return superimpose(a, b); // candidate

return isSubset(a, b.left) || isSubset(a, b.right);
}

private boolen superimpose(Node a, Node b) {
if (a == null)		return true;     // whatever 'b' is return true
if (b == null)		return false;  // 'a' is node but 'b' is not
if (a.data != b.data)		return false;

return superimpose(a.left, b.left) && superimpose(a.right, b.right);
}``````

This is just an idea, I hope it works.

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

Great solution but it has a little bug.

Consider the following case:

``````TreeA:
a
/
b

TreeB:
a
/
a
/
b``````

Also empty tree is Subset of every other I think.

Comment hidden because of low score. Click to expand.
2
of 2 votes

Hi dude, how about this one?

public boolean isSubset(Node a, Node b) {
if ( a== null || b == null) return false;
if (a.data == b.data && superimpose(a, b) return true;

return isSubset(a, b.left) || isSubset(a, b.right);
}

private boolen superimpose(Node a, Node b) {
if (a == null) return true;
if (b == null) return false;
if (a.data != b.data) return false;

return superimpose(a.left, b.left) && superimpose(a.right, b.right);
}

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

For every node in B, check if the subtree rooted at this node is equal to the tree A.

Solution in C.

``````bool subset(Node *A, Node *B) {
if (!A) return true;
bool check = check_subset(A, B);
if (check) return true;
return subset(A, B->left) || subset(A, B->right);
}

bool check_subset(Node *p, Node *q) {
if (!p) return true;
if (!q) return false;
if (p->id != q->id) return false;
return check_subset(p->left, q->left) && check_subset(p->right, q->right);
}``````

That trick of comparing graph traversal strings (present in the book) doesn't seem to work in this case, in which we look for subsets and not subtrees.

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

It is not very efficient. Assuming 'A' has m nodes and 'B' has n nodes, it takes O(n), where usually n>>m.
Better to find root of A inside the B, O(lg n) then traverse for checking subset by checking subset_left & subset_right. It will take O(m) and the final result will be O(m+lg n)

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

``````// API to check if Tree A is the subtree of B
// Input: A --- Node in tree A, the initial value should be the root of tree A
//           B --- Node in tree B, the initial value should be the root of tree B
//           parentMatched --- whether A's and B's parents are already matched
//                                          initial value should be FALSE
// Return: 1 --- yes, A is the sub tree of B
//              0 --- No! A is not the sub tree of B
// Note:

int isSubTree(Node *A, Node *B, int parentMatched)
{
if (A==NULL)
return 1;
if (B==NULL)
return 0;

if (parentMatched)
return (  A->data == B->data
&& isSubTree(A->left, B->left, parentMatched)
&& isSubTree(A->right, B->right, parentMatched)
);
else if (A->data == B->data) // just start to match
return isSubTree(A, B, 1);
else
{
int matched = isSubTree(A, B->left, parentMatched);
if (!matched)
matched = isSubTree(A, B->right, parentMatched);
return matched;
}
}``````

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

if A is:
0
1 2
3 4

B is:
1
3

will that be considered A is a subtree of B?

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

Generally, recursion is the more "intuitive" method to used to solve tree type problems. However, I personally believe that, if you can point out that recursion is cache unfriendly and sometimes wasteful of program stack, then you have an edge against other interviewees who did not point out this. Therefore, I think it is best that we DO NOT use recursion to solve this problem. Therefore, some key data structures to use would be the stack (for depth-first) and the queue (for breath-first). Let's take a look at this possible solution in Java:

Let's define the data structure:

``````public class BinaryTreeNode<T>
{
public T mData = null;
public BinaryTreeNode<T> mLeft = null;
public BinaryTreeNode<T> mRight = null;
}``````

The high-level description of our algorithm will be the following:

1. Find a node in the target tree that is the same
2. Once that's found, test systematically if all the target's nodes are the same as the other
3. If no such nodes are found, we do not have a sub-set

Let's define the equality test method:

``````private static boolean isSubTreeHelper(BinaryTreeNode a, BinaryTreeNode b)
{
if(a == b)
{
return true;
}
if(a == null || b == null)
{
return false;
}
LinkedList<BinaryTreeNode> a_queue = new LinkedList<BinaryTreeNode>();
LinkedList<BinaryTreeNode> b_queue = new LinkedList<BinaryTreeNode>();
a_queue.add(a);
b_queue.add(b);
while(a_queue.isEmpty() == false && b_queue.isEmpty() == false)
{
BinaryTreeNode a_node = a_queue.poll();
BinaryTreeNode b_node = b_queue.poll();
if(a_node.mData.equals(b_node.mData) == false)
{
return false;
}
if(a_node.mLeft != null)
{
a_queue.add(a_node.mLeft);
}
if(a_node.mRight != null)
{
a_queue.add(a_node.mRight);
}
if(b_node.mLeft != null)
{
b_queue.add(b_node.mLeft);
}
if(b_node.mRight != null)
{
b_queue.add(b_node.mRight);
}
}
return true;
}``````

The above method walks both tree in a breath-first left-to-right order to determine if each node are the same. If any nodes are different, false is returned. Note that the above method does not assume the two trees being compared must have the same depth. That is if either a or b finishes comparison and all the nodes that's been compared are the same, the method returns true regardless of b having any more nodes.

Given the above method, we can then write a method to find the first matching node and test at that node if there is an equality:

``````public static boolean isSubTree(BinaryTreeNode a, BinaryTreeNode b)
{
if(a == b)
{
return true;
}
if(a == null || b == null)
{
return false;
}
LinkedList<BinaryTreeNode> b_queue = new LinkedList<BinaryTreeNode>();
b_queue.add(b);
while(b_queue.isEmpty() == false)
{
BinaryTreeNode current_node = b_queue.poll();
if(current_node.mData.equals(a.mData) == true)
{
if(BinaryTree.isSubTreeHelper(a, current_node) == true)
{
return true;
}
}
if(current_node.mLeft != null)
{
b_queue.add(current_node.mLeft);
}
if(current_node.mRight != null)
{
b_queue.add(current_node.mRight);
}
}
return false;
}``````

Let's add a handy tree creation method that simply constructs a tree in a breath-first order from the given elements:

``````public static <T> BinaryTreeNode<T> createBinaryTree(T... elements)
{
if(elements == null)
{
return null;
}

LinkedList<BinaryTreeNode<T>> queue = new LinkedList<BinaryTreeNode<T>>();
BinaryTreeNode<T> root = new BinaryTreeNode<T>();
root.mData = elements[0];
int i = 1;
queue.add(root);
while(i < elements.length)
{
BinaryTreeNode<T> node = queue.poll();
node.mLeft = new BinaryTreeNode<T>();
node.mLeft.mData = elements[i++];
if(i >= elements.length)
{
break;
}
queue.add(node.mLeft);

node.mRight = new BinaryTreeNode<T>();
node.mRight.mData = elements[i++];
if(i >= elements.length)
{
break;
}
queue.add(node.mRight);
}

return root;
}``````

Here's the main test code:

``````public static void main(String[] args)
{
BinaryTreeNode<Integer> root = BinaryTree.createBinaryTree(1, 2);
root.mLeft.mRight = BinaryTree.createBinaryTree(2, 3, 4);
root.mLeft.mLeft = BinaryTree.createBinaryTree(5, 6);
root.mLeft.mRight.mLeft.mLeft = BinaryTree.createBinaryTree(7, 8, 9);
System.out.println("");
System.out.println(BinaryTree.isSubTree(BinaryTree.createBinaryTree(2, 3, 4), root));
}``````

Root looks like this:

``````1
/
/
2
/    \
5     2
/      / \
6     3  4
/
7
/ \
8  9``````

Please point out anything I left out! Thanks!

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

Do a preorder traversal of parent tree. Do a preorder traversal of child tree. See if the second string is a substring of the first string. The algo is O(n).

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

``````A:  0
2

B:  0
1  2``````

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

A binary tree can be converted into an array based on its property that: n's root is n*2 and n*2+1.
So, the problem becomes searching for substring.
Then,, the problem becomes quite simple.

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

Do pre-order for both A and B
Do in-order for both A and B

If both are same then B is a sub-tree of A

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

Complete code with test cases:

``````class Node {

Node left;
Node right;
int value;

Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}

public class BinaryTreeComparator {
public static void main(String [] args) {
Node master1 = new Node(6);
master1.left = new Node(5);
master1.right = new Node(12);
master1.left.left = new Node(4);
master1.left.right = new Node(7);
master1.right.left = new Node(8);
master1.right.right = new Node(10);

Node master2 = null;
Node master3 = new Node(10);

Node subtree1 = null;
Node subtree2 = new Node(10);
Node subtree3 = new Node(5);
subtree3.left = new Node(4);
subtree3.right = new Node (7);

System.out.println("Master1 and Subtree1: " + checkSubTree(master1, subtree1));
System.out.println("Master1 and Subtree2: " + checkSubTree(master1, subtree2));
System.out.println("Master1 and Subtree3: " + checkSubTree(master1, subtree3));
System.out.println("Master2 and Subtree1: " + checkSubTree(master2, subtree1));
System.out.println("Master2 and Subtree2: " + checkSubTree(master2, subtree2));
System.out.println("Master2 and Subtree3: " + checkSubTree(master2, subtree3));
System.out.println("Master3 and Subtree1: " + checkSubTree(master3, subtree1));
System.out.println("Master3 and Subtree2: " + checkSubTree(master3, subtree2));
System.out.println("Master3 and Subtree3: " + checkSubTree(master3, subtree3));

Node master4 = master1;
master4.left.left.left = new Node(1);

System.out.println("Master4 and Subtree1: " + checkSubTree(master4, subtree1));
System.out.println("Master4 and Subtree2: " + checkSubTree(master4, subtree2));
System.out.println("Master4 and Subtree3: " + checkSubTree(master4, subtree3));
}

public static boolean checkSubTree(Node master, Node sub) {
return (compareTrees(master, sub) ||
(master != null && master.left != null && checkSubTree(master.left, sub)) ||
(master != null && master.right != null && checkSubTree(master.right, sub)));
}

public static boolean compareTrees(Node masterTree, Node subTree) {
// Subtree is allowed to be null
if (subTree == null) {
return true;
}
// Master cannot be null, if subtree is null.
else if (masterTree == null) {
return false;
}
// At this point, both the trees are non-null.
if (masterTree.value != subTree.value) {
return false;
}
return (compareTrees(masterTree.left, subTree.left) && compareTrees(masterTree.right, subTree.right));
}
}``````

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

``````public class SubTree {

private static class BTNode {
public int data;
public BTNode left;
public BTNode right;

public BTNode(int data_) {
data = data_;
}

public BTNode(int data_, BTNode left_, BTNode right_) {
data = data_;
left = left_;
right = right_;
}
}

public static boolean isSubTree(BTNode A, BTNode B) {
// base cases
if (A == null) return true;
if (B == null) return false;  // A != null && B == null

// recursive cases (neither A nor B are null)
if (A.data == B.data && isSubTree(A.left, B.left) && isSubTree(A.right, B.right))
return true;
else
return isSubTree(A, B.left) || isSubTree(A, B.right);
}

public static void main(String[] args) {
// create some trees to test the method

BTNode n1 = new BTNode(1);
BTNode n2 = new BTNode(2);
BTNode n3 = new BTNode(3);
BTNode n4 = new BTNode(4);
BTNode n5 = new BTNode(5);
BTNode n6 = new BTNode(6);
BTNode n7 = new BTNode(7);
BTNode n8 = new BTNode(8);

n1.left = n2;
n1.right = n3;

n2.left = n4;
n2.right = n5;

n3.left = n6;
n3.right = n7;

n4.left = n8;

BTNode a2 = new BTNode(2);
BTNode a4 = new BTNode(4);
BTNode a5 = new BTNode(5);

a2.left = a4;
a2.right = a5;

System.out.println("True: " + isSubTree(a2, n1));
System.out.println("True: " + isSubTree(a2, n2));
System.out.println("False: " + isSubTree(a2, n3));
System.out.println("False: " + isSubTree(a2, n4));
}

}``````

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

``````#include <iostream>
#include <list>
struct node {
int val;
node* left;
node* right;
};

// DFS
void DFS(node* tree, int value, std::list<node*>& listOfFound) {
if(tree == NULL) { return; }
if(tree->val == value) { listOfFound.push_back(tree); }
DFS(tree->left, value, listOfFound);
DFS(tree->right, value, listOfFound);
}

// is B a subtree of A
bool isSubTreeInner(node* rootA, node* rootB) {
if(rootA==NULL && rootB==NULL) { return true; }
if(rootA->val!=rootB->val) { return false; }
return isSubTreeInner(rootA->left, rootB->left) && isSubTreeInner(rootA->right, rootB->right);
}

bool isSubTree(node* A, node* B) {
if(A==NULL || B==NULL) { return false; }
std::list<node*> listOfFound;
DFS(A,B.val,listOfFound);
node* candidate;
bool verdict;
while(!listOfFound.empty()) {
candidate = listOfFound.front();
listOfFound.pop_front();
verdict = isSubTreeInner(candidate,B);
if(verdict)	{ return verdict; }
}
return false;
}``````

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

``````#include <iostream>
#include <list>
struct node {
int val;
node* left;
node* right;
};

// DFS
void DFS(node* tree, int value, std::list<node*>& listOfFound) {
if(tree == NULL) { return; }
if(tree->val == value) { listOfFound.push_back(tree); }
DFS(tree->left, value, listOfFound);
DFS(tree->right, value, listOfFound);
}

// is B a subtree of A
bool isSubTreeInner(node* rootA, node* rootB) {
if(rootA==NULL && rootB==NULL) { return true; }
if(rootA->val!=rootB->val) { return false; }
return isSubTreeInner(rootA->left, rootB->left) && isSubTreeInner(rootA->right, rootB->right);
}

bool isSubTree(node* A, node* B) {
if(A==NULL || B==NULL) { return false; }
std::list<node*> listOfFound;
DFS(A,B.val,listOfFound);
node* candidate;
bool verdict;
while(!listOfFound.empty()) {
candidate = listOfFound.front();
listOfFound.pop_front();
verdict = isSubTreeInner(candidate,B);
if(verdict)	{ return verdict; }
}
return false;
}``````

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

``````#include <iostream>
#include <list>
struct node {
int val;
node* left;
node* right;
};

// DFS
void DFS(node* tree, int value, std::list<node*>& listOfFound) {
if(tree == NULL) { return; }
if(tree->val == value) { listOfFound.push_back(tree); }
DFS(tree->left, value, listOfFound);
DFS(tree->right, value, listOfFound);
}

// is B a subtree of A
bool isSubTreeInner(node* rootA, node* rootB) {
if(rootA==NULL && rootB==NULL) { return true; }
if(rootA->val!=rootB->val) { return false; }
return isSubTreeInner(rootA->left, rootB->left) && isSubTreeInner(rootA->right, rootB->right);
}

bool isSubTree(node* A, node* B) {
if(A==NULL || B==NULL) { return false; }
std::list<node*> listOfFound;
DFS(A,B.val,listOfFound);
node* candidate;
bool verdict;
while(!listOfFound.empty()) {
candidate = listOfFound.front();
listOfFound.pop_front();
verdict = isSubTreeInner(candidate,B);
if(verdict)	{ return verdict; }
}
return false;
}``````

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

``````public class SubsetCheck {
public static void main(String[] args) {
Node A = new Node(5, new Node(4, null, null), new Node(7, null, null));
Node B = new Node(6, new Node(5, new Node(4, null,
null), new Node(7, null, null)), new Node(12, new Node(8,
null, null), new Node(10, null, null)));

System.out.println(isSubset(A, B));
}

public static boolean isSubset(Node A, Node B) {
if (A == null)
return true;
if (B == null)
return false;

if (A.value == B.value) {
return (isSubset(A.left, B.left) && isSubset(A.right, B.right))
|| (isSubset(A, B.left) || isSubset(A, B.right));
}
return (isSubset(A, B.left) || isSubset(A, B.right));
}

}

class Node {
int value;
Node left;
Node right;

public Node(int value, Node left, Node right) {
this.value = value;
this.right = right;
this.left = left;
}
}``````

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

``````public class SubsetCheck {
public static void main(String[] args) {
Node A = new Node(5, new Node(4, null, null), new Node(7, null, null));
Node B = new Node(6, new Node(5, new Node(4, null,
null), new Node(7, null, null)), new Node(12, new Node(8,
null, null), new Node(10, null, null)));

System.out.println(isSubset(A, B));
}

public static boolean isSubset(Node A, Node B) {
if (A == null)
return true;
if (B == null)
return false;

if (A.value == B.value) {
return (isSubset(A.left, B.left) && isSubset(A.right, B.right))
|| (isSubset(A, B.left) || isSubset(A, B.right));
}
return (isSubset(A, B.left) || isSubset(A, B.right));
}

}

class Node {
int value;
Node left;
Node right;

public Node(int value, Node left, Node right) {
this.value = value;
this.right = right;
this.left = left;
}
}``````

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

``````public class SubsetCheck {
public static void main(String[] args) {
Node A = new Node(5, new Node(4, null, null), new Node(7, null, null));
Node B = new Node(6, new Node(5, new Node(4, null,
null), new Node(7, null, null)), new Node(12, new Node(8,
null, null), new Node(10, null, null)));

System.out.println(isSubset(A, B));
}

public static boolean isSubset(Node A, Node B) {
if (A == null)
return true;
if (B == null)
return false;

if (A.value == B.value) {
return (isSubset(A.left, B.left) && isSubset(A.right, B.right))
|| (isSubset(A, B.left) || isSubset(A, B.right));
}
return (isSubset(A, B.left) || isSubset(A, B.right));
}

}

class Node {
int value;
Node left;
Node right;

public Node(int value, Node left, Node right) {
this.value = value;
this.right = right;
this.left = left;
}
}``````

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

``````class BstNode
{
public:

BstNode(int _data) : data(_data), left(nullptr), right(nullptr) {};

int data;
BstNode* left;
BstNode* right;
};

bool can_superimpose(BstNode* a, BstNode* b)
{
if (nullptr == a) return true;
if (nullptr == b) return false;
return a->data == b->data && can_superimpose(a->left, b->left) && can_superimpose(a->right, b->right);
}

bool is_sub_tree(BstNode* a, BstNode* b)
{
if (nullptr == a) return true;
if (nullptr == b) return false;
auto value = a->data;
if (value == b->data && can_superimpose(a, b)) return true;
return is_sub_tree(a, b->left) || is_sub_tree(a, b->right);
}

void test_is_sub_tree()
{
auto a = new BstNode(5);
a->left = new BstNode(4);
a->right = new BstNode(7);

auto b = new BstNode(6);
b->left = new BstNode(5);
b->right = new BstNode(12);
b->left->left = new BstNode(4);
b->left->right = new BstNode(7);
b->right->left = new BstNode(8);
b->right->right = new BstNode(10);
b->left->left->left = new BstNode(1);

assert(is_sub_tree(a, b));
b->left->right->data = 42;
assert(!is_sub_tree(a, b));
delete b->left->right;
b->left->right = nullptr;
assert(!is_sub_tree(a, b));
}``````

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

``````package treeAndGraphs;

/**
*
* @author mattoop
*/
public class BinarySubtree {

static Node root1,root2;

/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
boolean areIdentical(Node node1, Node node2) {

/* base cases */
if (node1 == null && node2 == null) {
return true;
}

if (node1 == null || node2 == null) {
return false;
}

/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (node1.data == node2.data
&& areIdentical(node1.left, node2.left)
&& areIdentical(node1.right, node2.right));
}

/* This function returns true if S is a subtree of T, otherwise false */
boolean isSubtree(Node T, Node S) {

/* base cases */
if (S == null) {
return true;
}

if (T == null) {
return false;
}

/* Check the tree with root as current node */
if (areIdentical(T, S)) {
return true;
}

/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T.left, S)
|| isSubtree(T.right, S);
}

public static void main(String args[]) {

}
}``````

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