Facebook Interview Question Interns
Country: United States
Interview Type: Phone Interview
It depends on the definition of 'first'. Smallest depth? Most left? Most right? Bottom up?
Also are you given two root nodes? Two lists? pre-order/post-order/in-order?
Assume you are given two root nodes and the definition of first mismatch is the mismatch at the smallest depth, and in an order of left-to-right.
Use two queues to do BFS on the (node, depth) tuple, and return the first mismatch, the catch is to store Null node into the queue as well.
Trivial Method:
a. DFS both trees and save the leaves of each tree in two separate lists
b. Compare the two lists one-by-one and return the first non-matching pair.
I feel like the method above is very inefficient. Because you have to make a list of all the nodes in every case unnecessarily when you have a chance to early exit.
One thing I can think of right now is to use multi-threading. By the help of a mutex, each tree will traverse (depth-first) 1 leaf at a time, save it to a common container, and return when there's a mismatch.
For example:
- Tree 1 starts DFS, finds a leaf, saves it to a tmp variable, releases the mutex.
- Tree 2 gets the mutex and does DFS until it finds a leaf, and compares the leaf value to tmp. If there's a mismatch, function returns, if it's matching, it releases mutex, and Tree 1 takes the mutex, and back to step (1).
Here is a solution using DFS and then comparing two arrays of leaves. Written in Swift.
Also another solution could be:
Create a generator of leaves based on a tree and ask for leaves one by one, and instead of creating array of leaves you could stop after getting two different leaves. This way you could avoid traversing through entire tree and stop right after detecting a difference.
import Foundation
class Tree {
typealias LeavesPair = (leaf1: String?, leaf2: String?)
private class Node {
let val: String
var left: Node?
var right: Node?
init(val: String) {
self.val = val
}
}
private var root: Node?
static func findDifferenceInLeaves(tree1: Tree, tree2: Tree) -> LeavesPair {
var leaves1 = [Node]()
var leaves2 = [Node]()
collectLeaves(root: tree1.root, leaves: &leaves1)
collectLeaves(root: tree2.root, leaves: &leaves2)
let minCount = min(leaves1.count, leaves2.count)
for idx in 0..<minCount {
if leaves1[idx].val != leaves2[idx].val {
return LeavesPair(leaves1[idx].val, leaves2[idx].val)
}
}
return LeavesPair(nil, nil)
}
init(array: [String?]) {
array.flatMap({ $0 }).forEach { insert(root: &root, val: $0) }
}
func insert(val: String) {
insert(root: &root, val: val)
}
private func insert(root: inout Node?, val: String) {
if let root = root {
if val < root.val {
if root.left != nil {
insert(root: &root.left, val: val)
} else {
root.left = Node(val: val)
}
} else {
if root.right != nil {
insert(root: &root.right, val: val)
} else {
root.right = Node(val: val)
}
}
} else {
root = Node(val: val)
}
}
private static func collectLeaves(root: Node?, leaves: inout [Node]) {
guard let root = root else { return }
if root.left == nil && root.right == nil {
leaves.append(root)
}
collectLeaves(root: root.left, leaves: &leaves)
collectLeaves(root: root.right, leaves: &leaves)
}
}
// Test
let arr1: [String?] = ["A", "B", "C", "D", "E", nil, nil]
let tree1 = Tree(array: arr1)
let arr2: [String?] = ["A", "D", "B"]
let tree2 = Tree(array: arr2)
let diff = Tree.findDifferenceInLeaves(tree1: tree1, tree2: tree2)
Wouldn't this work?
public static Pair<Integer, Integer> firstUnmatchedLeaf(Node* first, Node* second){
//null point checks and all go here
if(first.data != second.data) return new Pair<Integer, Integer>(first.data, second.data);
Pair<Integer, Integer> out = firstUnmatchedLeaf(first.left, second.left);
if (out != null) return out;
out = firstUnmatchedLeaf(first.right, second.right);
if (out != null) return out;
return null;
}
Wouldn't this work?
public static Pair<Integer, Integer> firstUnmatchedLeaf(Node* first, Node* second){
//null point checks and all go here
if(first.data != second.data) return new Pair<Integer, Integer>(first.data, second.data);
Pair<Integer, Integer> out = firstUnmatchedLeaf(first.left, second.left);
if (out != null) return out;
out = firstUnmatchedLeaf(first.right, second.right);
if (out != null) return out;
return null;
}
Can you provide more example?
Solution approach:
Any kind of tree traversal, but create a list of leaves from left to right for both Trees and compare both the list and 1st mismatch is the pair?
But if the leaf list is:
Tree1 : [1, 2, 3]
Tree2 : [1, 2, 3, 4]
In this case, what would be the output?
public static void nonMatchingLeaves(BinaryTreeNode root1, BinaryTreeNode root2){
// 1. Create empty stacks stack1 and stack2. These stacks are going
// to be used for iterative traversals.
Stack<BinaryTreeNode> s1 = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> s2 = new Stack<BinaryTreeNode>();
//2. insert roots in stack
s1.push(root1);
s2.push(root2);
//3. Stores current leaf nodes of tree1 and tree2
BinaryTreeNode temp1 = null;
BinaryTreeNode temp2 = null;
// 4. traverse both leaves using stacks
while(!s1.isEmpty() || !s2.isEmpty()){
// get next leaf node in tree1
temp1 = determineLeaf(s1);
// get next leaf node in tree2
temp2 = determineLeaf(s2);
if(temp1 == null && temp2 == null){
System.out.println("null null");
return;
}else if(temp1 == null){
System.out.println("null " + temp2.getData());
return;
}else if(temp2 == null){
System.out.println("null " + temp1.getData());
return;
}
// if leaves do not match, return the pair
else if(temp1.getData() != temp2.getData()){
System.out.println(temp1.getData() + " " + temp2.getData());
return;
}
}
}
private static BinaryTreeNode determineLeaf(Stack<BinaryTreeNode> stack){
BinaryTreeNode temp = null;
while(!stack.isEmpty()){
temp = stack.pop();
if(isLeaf(temp)){
return temp;
}
if(temp.right != null)
stack.push(temp.right);
if(temp.left != null)
stack.push(temp.left);
}
return null;
}
private static boolean isLeaf(BinaryTreeNode node){
return (node.right == null && node.left == null);
}
public static void nonMatchingLeaves(BinaryTreeNode root1, BinaryTreeNode root2){
// 1. Create empty stacks stack1 and stack2. These stacks are going
// to be used for iterative traversals.
Stack<BinaryTreeNode> s1 = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> s2 = new Stack<BinaryTreeNode>();
//2. insert roots in stack
s1.push(root1);
s2.push(root2);
//3. Stores current leaf nodes of tree1 and tree2
BinaryTreeNode temp1 = null;
BinaryTreeNode temp2 = null;
// 4. traverse both leaves using stacks
while(!s1.isEmpty() || !s2.isEmpty()){
// get next leaf node in tree1
temp1 = determineLeaf(s1);
// get next leaf node in tree2
temp2 = determineLeaf(s2);
if(temp1 == null && temp2 == null){
System.out.println("null null");
return;
}else if(temp1 == null){
System.out.println("null " + temp2.getData());
return;
}else if(temp2 == null){
System.out.println("null " + temp1.getData());
return;
}
// if leaves do not match, return the pair
else if(temp1.getData() != temp2.getData()){
System.out.println(temp1.getData() + " " + temp2.getData());
return;
}
}
}
private static BinaryTreeNode determineLeaf(Stack<BinaryTreeNode> stack){
BinaryTreeNode temp = null;
while(!stack.isEmpty()){
temp = stack.pop();
if(isLeaf(temp)){
return temp;
}
if(temp.right != null)
stack.push(temp.right);
if(temp.left != null)
stack.push(temp.left);
}
return null;
}
private static boolean isLeaf(BinaryTreeNode node){
return (node.right == null && node.left == null);
}
Instead of finding all the list of leafs in both tree, we can query for the next leaf from each of the trees.If two leafs are not same then we have our first non matching leaf pair and thus we can exit early.
+ (NSDictionary<NSNumber *, MapNode *> *)firstNonMatchingLeafPairFromtree:(Map *)treeOne treeTwo:(Map *)treeTwo {
Stack<MapNode *> *stackOne = [[Stack alloc] initWithObject:treeOne.root];
Stack<MapNode *> *stackTwo = [[Stack alloc] initWithObject:treeTwo.root];
MapNode *leafOne = [[self class] leafForTreeWithStack:stackOne];
MapNode *leafTwo = [[self class] leafForTreeWithStack:stackTwo];
while(leafOne && leafTwo) {
if (![leafOne.value isEqualToNumber:leafTwo.value]) {
return @{@(1): leafOne, @(2): leafTwo};
}
else {
leafOne = [[self class] leafForTreeWithStack:stackOne];
leafTwo = [[self class] leafForTreeWithStack:stackTwo];
}
}
return nil;
}
+ (MapNode *)leafForTreeWithStack:(Stack *)stack {
MapNode *node = nil;
while (stack.count > 0) {
node = stack.pop;
if (!node.left && !node.right) {
return node;
}
if (node.right) {
[stack push:node.right];
}
if (node.left) {
[stack push:node.left];
}
}
return nil;
}
This is an Objective-C solution, the idea is get leaves from each tree and then compare each other in order to get non-matching leaves, I came with this solution considering the case when tree1 has 2 levels and tree 2 has 4 levels
-(NSMutableArray *)getNotMatchingLeaves:(TreeNode *)root1 and:(TreeNode *)root2{
if(root1 == nil && root2 == nil){
return nil;
}
NSMutableArray *stack1 = [NSMutableArray new];
NSMutableArray *stack2 = [NSMutableArray new];
[stack1 addObject:root1];
[stack2 addObject:root2];
NSMutableArray *leaves1 = [NSMutableArray new];
NSMutableArray *leaves2 = [NSMutableArray new];
while([stack1 count] > 0 || [stack2 count] > 0){
if([stack1 count] > 0){
root1 = [stack1 objectAtIndex:0];
[stack1 removeObjectAtIndex:0];
if(root1.left == nil && root1.rigth == nil){
[leaves1 addObject:[NSNumber numberWithInt:root1.value]];
}
if(root1.left != nil){
[stack1 addObject: root1.left];
}
if(root1.rigth != nil){
[stack1 addObject: root1.rigth];
}
}
if([stack2 count] > 0){
root2 = [stack2 objectAtIndex:0];
[stack2 removeObjectAtIndex:0];
if(root2.left == nil && root2.rigth == nil){
[leaves2 addObject:[NSNumber numberWithInt:root2.value]];
}
if(root2.left != nil){
[stack2 addObject: root2.left];
}
if(root2.rigth != nil){
[stack2 addObject: root2.rigth];
}
}
}
leaves1 = [leaves1 sortedArrayUsingSelector:@selector(compare:)];
leaves2 = [leaves2 sortedArrayUsingSelector:@selector(compare:)];
NSMutableArray *result = [self getUniqueItemsFromArray:leaves1 andArray:leaves2];
return result;
}
-(NSMutableArray *)getUniqueItemsFromArray:(NSMutableArray *)array1 andArray:(NSMutableArray *)array2{
int i = 0;
int j = 0;
NSMutableArray *result = [NSMutableArray new];
while(i < [array1 count] && j < [array2 count]){
if([array1[i] intValue] > [array2[j] intValue]){
[result addObject:[NSNumber numberWithInt:[array2[j] intValue]]];
j++;
}
else if([array1[i] intValue] < [array2[j] intValue]){
[result addObject:[NSNumber numberWithInt:[array1[i] intValue]]];
i++;
}
else{
i++;
j++;
}
}
while(i < [array1 count]){
[result addObject:[NSNumber numberWithInt:[array1[i] intValue]]];
}
while(j < [array2 count]){
[result addObject:[NSNumber numberWithInt:[array2[j] intValue]]];
}
return result;
}
I'm not a fan of this question. Not sure whether it's the original question itself or the representation given, but I'm saying ambiguous. This is why.
Additional information provided in the comments states that the traversals provided are in-order and the root node is given. Presumably let's assume that the tree itself is ordered; otherwise the question becomes even more ambiguous.
For example, looking at in-order traversals on the first tree starting from node 'D', it's easy to see that at least two trees may exist that yield the same traversal ordering. This affects what nodes are leaves and which nodes are not, which an essential part of the question.
D
/ \
C E
/
B
/
A
D
/ \
B E
/ \
A C
If the traversal was pre-ordered, then the situation would be more clear; leaf nodes could be detected with a stack and array traversal in O(nlogn) time and O(logn) space. But, that's not how the problem is stated. I'm moving on unless somebody tells me I'm wrong or provides additional details that have not yet been given.
- mrsurajpoudel.wordpress.com October 04, 2016Node* leaf_from_tree(stack<Node*>& inorder_tree) { while(!inorder_tree.empty()) { Node *top = inorder_tree.top(); inorder_tree.pop(); if( top->right == NULL && top->left == NULL) return top; else if(top->right != NULL) { Node *node = top->right; while( node != NULL) { inorder_tree.push(node); node = node->left; } } } return NULL; } void initialize(Node* root, stack<Node*>& st) { Node *node = root; while(node != NULL) { st.push(node); node = node->left; } } pair<int, int> first_unmatched_leaves(Node* root1, Node* root2) { stack<Node*> tree1; stack<Node*> tree2; initialize(root1, tree1); initialize(root2, tree2); Node *leaf1, *leaf2; do{ leaf1 = leaf_from_tree(tree1); leaf2 = leaf_from_tree(tree2); if(leaf1->value != leaf2->value) return make_pair(leaf1->value, leaf2->value); }while(leaf1 != NULL && leaf2 != NULL); return make_pair(-1, -1); }