Google Interview Question
Country: United States
Interview Type: Phone Interview
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.
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);
}
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.
// 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;
}
}
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!
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).
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));
}
}
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));
}
}
#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;
}
#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;
}
#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;
}
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;
}
}
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;
}
}
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;
}
}
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));
}
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[]) {
}
}
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.
- autoboli January 12, 2015