Facebook Interview Question
Software DevelopersCountry: United States
package something;
import java.util.*;
public class FindIfNodesInListAreFromABinaryTree {
public static void main(String[] args) {
System.out.println("== valid tree");
List<Node> tree = cleanTree();
boolean areTree = isValidTree(tree);
System.out.println(areTree); // will PRINT true
System.out.println("== forest ");
tree = twoTrees();
areTree = isValidTree(tree);
System.out.println(areTree); // will PRINT false
// tree with at last one node where node.left is pointing to
// some ancestor
System.out.println("== invalid tree, with cycle");
tree = cyclicTree();
areTree = isValidTree(tree);
System.out.println(areTree); // will PRINT true
}
private static boolean isValidTree(List<Node> listOfNodes) {
Objects.requireNonNull(listOfNodes);
if (listOfNodes.size() <= 1) return true;
Set<Node> roots = findRoots(listOfNodes);
if (roots.size() != 1) {
System.out.printf("No single root could be found, found %d roots %n", roots.size());
return false;
}
Node root = roots.iterator().next();
System.out.println("root is " + root.d);
Set<Integer> allNodes = new HashSet<>();
for (Node n : listOfNodes)
allNodes.add(System.identityHashCode(n));
Set<Integer> allNodesCheck = new HashSet<>();
// visit all nodes in possible tree and add to allNodesCheck
try {
saveIdentities(root, allNodes, allNodesCheck);
} catch (Exception e) {
System.out.println("Cycle detected..");
return false;
}
return allNodes.equals(allNodesCheck);
}
/**
* as you descend the tree do the following for each node
* if node is null return
* find hashCode of this Node object
* check that this hash exists in the list of all hashCodes
* check that this hash was NOT seen before
* add this to the list of seen hash codes
* recurse with left subtree
* recurse with right subtree
*
* @param root
* @param allNodes
* @param allNodesCheck
* @throws Exception
*/
private static void saveIdentities(Node root, Set<Integer> allNodes, Set<Integer> allNodesCheck) throws Exception {
if (root == null) return;
int h = System.identityHashCode(root);
if (!allNodes.contains(h)) throw new Exception("Node in tree not found in the list ");
if (allNodesCheck.contains(h)) throw new Exception("Possible loop ");
//we established that it is in the original list and it was not seen earlier
//we now add this node to allNodesCheck
allNodesCheck.add(h);
saveIdentities(root.left, allNodes, allNodesCheck);
saveIdentities(root.right, allNodes, allNodesCheck);
}
/**
* The root node is the one that is NOT pointed to by anyone else
*
* @param listOfNodes
* @return
*/
private static Set<Node> findRoots(List<Node> listOfNodes) {
Set<Node> allNodes = new HashSet<>();
allNodes.addAll(listOfNodes);
for (Node n : listOfNodes) {
allNodes.remove(n.left);
allNodes.remove(n.right);
}
System.out.println("size of remaining list that should contain root =" + allNodes.size());
return allNodes;
}
// == mostly boiler plate
private static List<Node> cyclicTree() {
Node n1 = Node.of(1);
Node n3 = Node.of(3);
Node n5 = Node.of(5);
Node n6 = Node.of(6);
Node n12 = Node.of(12);
Node n7 = Node.of(7);
List<Node> list = new ArrayList<>();
list.add(n1);
list.add(n3);
list.add(n5);
list.add(n6);
list.add(n12);
list.add(n7);
n1.left = n3;
n1.right = n5;
n3.left = n6;
n3.right = n12;
n5.left = n7;
n7.right = n3; // a node in RIGHT subtree is pointing to a node in the left subtree
return list;
}
private static List<Node> twoTrees() {
Node n2 = Node.of(2);
Node n7 = Node.of(7);
Node n5 = Node.of(5);
n2.left = n7;
n2.right = n5;
Node n11 = Node.of(11);
Node n15 = Node.of(15);
n11.left = n15;
List<Node> list = new ArrayList<>();
list.add(n2);
list.add(n7);
list.add(n5);
list.add(n11);
list.add(n15);
return list;
}
private static List<Node> cleanTree() {
Node n2 = Node.of(2);
Node n7 = Node.of(7);
Node n5 = Node.of(5);
Node n11 = Node.of(11);
Node n22 = Node.of(22);
Node n12 = Node.of(12);
Node n13 = Node.of(13);
Node n15 = Node.of(15);
List<Node> list = new ArrayList<>();
list.add(n2);
list.add(n7);
list.add(n5);
list.add(n11);
list.add(n22);
list.add(n12);
list.add(n13);
list.add(n15);
n2.left = n7;
n2.right = n5;
n7.right = n11;
n11.left = n22;
n5.left = n12;
n5.right = n13;
n13.left = n15;
return list;
}
private static class Node {
Node left, right;
int d;
public Node(int d) {
this.d = d;
}
public static Node of(int d) {
return new Node(d);
}
}
}
/*
I wanted to mention here how I have interpreted this problem!
Assume you have a valid binary tree. Take each node from this tree and
add these nodes to a list (array). This is the list the problem is talking about.
While the nodes are placed in this list - they still point to their
original left tree and right sub tree
The method should return TRUE if the list had nodes
from a valid binary tree
The method should return FALSE if the list had nodes from more
than one distinct binary tree ( forest )
The method should return FALSE if the list had nodes from a binary
tree that contained cycles ( not a tree in the first place)
*/
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
class Node {
public:
Node()
{
left_ = right_ = NULL;
}
Node *left_, *right_;
};
bool AddToChildren(Node *n, Node *parent, unordered_set<Node *> &children)
{
if (n) {
if (n == parent ||
children.find(n) != children.end())
{
return false;
}
children.insert(n);
}
return true;
}
bool IsValidTree(vector<Node *> const &nodes)
{
unordered_set<Node *> children;
for (Node *n : nodes) {
if (n) {
if (!AddToChildren(n->left_, n, children) ||
!AddToChildren(n->right_, n, children))
{
return false;
}
}
}
if (children.size() != nodes.size() - 1) {
return false;
}
for (Node *n : nodes) {
children.erase(n);
}
return children.empty();
}
int main() {
/*
(1)
/ \
(2) (3)
/ \
(4) (5)
*/
Node n1, n2, n3, n4, n5;
n1.left_ = &n2;
n1.right_ = &n3;
n2.left_ = &n4;
n2.right_ = &n5;
cout << IsValidTree({&n1, &n2, &n3, &n4, &n5}) << "\n";
return 0;
}
import java.util.*;
class CheckGraph {
static class Node {
int val;
Node left, right;
Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
static boolean isValid(List<Node> nodes) {
return nodes.stream()
.anyMatch(n -> {
Set<Node> toFind = new HashSet<>(nodes);
return isValidInternal(n, toFind) &&
toFind.size() == 0;
});
}
private static boolean isValidInternal(Node head, Set<Node> toFind) {
if (toFind.remove(head)) {
return (head.left == null || isValidInternal(head.left, toFind)) &&
(head.right == null || isValidInternal(head.right, toFind));
} else {
//cycle
return false;
}
}
//smoke test
public static void main(String[] args) {
Node n = new Node(1,
new Node(2, new Node(3, null, null), new Node(4, null, null)),
new Node(5, new Node(6, null, null), new Node(7, null, null)));
List<Node> nodes = new ArrayList<>(
Arrays.asList(n.left.left, n.right.left, n.left.right, n.right.right, n.left, n.right, n));
System.err.println(isValid(nodes)); //prints true
//add cycle
n.right.right.right = n.right.left;
System.err.println(isValid(nodes)); //prints false
//add external node
nodes.add(new Node(42, null, null));
System.err.println(isValid(nodes)); //prints false
}
}
1. Create an array that would store the number of parents of each node
2. Iterate through the given array of nodes and start filling the new array.
3. The given nodes form a valid binary tree if:
a. Number of nodes with no parents = 1 (the root).
b. No nodes have more than one parent.
c. Doing a tree traversal from the root node covers all the nodes in the list and no external node is referenced.
import java.util.*;
public class MyClass {
public static void main(String args[]) {
List<Node> list = new ArrayList<Node>();
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
Node g = new Node("G");
Node b = new Node(d, e, "B");
Node c = new Node(f, g, "C");
Node a = new Node(b, c, "A");
Node x = new Node("X");
list.add(a);list.add(b);list.add(c);list.add(d);
list.add(e);list.add(f);list.add(g);list.add(x);
System.out.println(isValidTree(list));
}
static boolean isValidTree(List<Node> list){
boolean visited[] = new boolean[list.size()];
boolean notAloof[] = new boolean[list.size()];
for(Node item:list){
if(item != null){
if(item.left !=null && item.right !=null)
if(!list.contains(item.left) || !list.contains(item.right)) return false;
visited[list.indexOf(item)] = true;
if(item.left !=null && item.right !=null){
if(visited[list.indexOf(item.left)] || visited[list.indexOf(item.right)]) return false;
notAloof[list.indexOf(item.right)] = true;
notAloof[list.indexOf(item.left)] = true;
}
if(item.left !=null && item.right !=null)
notAloof[list.indexOf(item)] = notAloof[list.indexOf(item.right)] || notAloof[list.indexOf(item.left)];
if(!notAloof[list.indexOf(item)]) return false;
}
}
return true;
}
static class Node{
Node left;
Node right;
Object data;
Node(Object a){
left = right = null;
data = a;
}
Node(Node a, Node b, Object d){
left = a;
right = b;
data = d;
}
}
}
import java.util.*;
public class MyClass {
public static void main(String args[]) {
List<Node> list = new ArrayList<Node>();
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
Node g = new Node("G");
Node b = new Node(d, e, "B");
Node c = new Node(f, g, "C");
Node a = new Node(b, c, "A");
Node x = new Node("X");
list.add(a);list.add(b);list.add(c);list.add(d);
list.add(e);list.add(f);list.add(g);list.add(x);
System.out.println(isValidTree(list));
}
static boolean isValidTree(List<Node> list){
boolean visited[] = new boolean[list.size()];
boolean notAloof[] = new boolean[list.size()];
for(Node item:list){
if(item != null){
if(item.left !=null && item.right !=null)
if(!list.contains(item.left) || !list.contains(item.right)) return false;
visited[list.indexOf(item)] = true;
if(item.left !=null && item.right !=null){
if(visited[list.indexOf(item.left)] || visited[list.indexOf(item.right)]) return false;
notAloof[list.indexOf(item.right)] = true;
notAloof[list.indexOf(item.left)] = true;
}
if(item.left !=null && item.right !=null)
notAloof[list.indexOf(item)] = notAloof[list.indexOf(item.right)] || notAloof[list.indexOf(item.left)];
if(!notAloof[list.indexOf(item)]) return false;
}
}
return true;
}
static class Node{
Node left;
Node right;
Object data;
Node(Object a){
left = right = null;
data = a;
}
Node(Node a, Node b, Object d){
left = a;
right = b;
data = d;
}
}
}
Solution using Python code. Find the node with max height. It should be the root. From the root traverse using BFS and conclude if it's a valid tree.
from Queue import Queue
def get_height(node):
# algorithm will be O(n)
if node is None:
return 0
return 1 + max(get_height(node.left), get_height(node.right))
def is_valid_binary_tree(nodes):
if nodes is None or len(nodes) == 0:
return True
root = nodes[0]
valid = {}
for node in nodes:
x = get_height(node)
valid[node] = True
if x > get_height(root):
root = node
# Found the highest node, now use hashmap
bfs_queue = Queue()
bfs_queue.put(root)
while not bfs_queue.empty():
current = bfs_queue.get()
if current.left is not None:
bfs_queue.put(current.left)
if current.right is not None:
bfs_queue.put(current.right)
if current not in nodes:
return False
else:
del valid[current]
nodes.remove(current)
return len(nodes) == 0
if __name__ == '__main__':
n1 = TreeNode(0)
n2 = TreeNode(1)
n3 = TreeNode(2)
n4 = TreeNode(3)
n5 = TreeNode(4)
n6 = TreeNode(6)
n1.left = n2
n1.right = n3
n2.left = n4
n3.right = n5
print is_valid_binary_tree([n1, n2, n3, n4, n5])
print is_valid_binary_tree([n1])
print is_valid_binary_tree([n1, n2, n3, n4, n5, n6])
print is_valid_binary_tree([n1, n1, n3, n4, n5, n6])
It can be done in O(n) time complexity (save the list into a Hashset for fast look up).
Iterate each node in the list and check the following conditions:
1. Its left and right node are null.We move the node from the list to a hashset, called "lookForParent".
2. Its left or right node does not belong to the list nor appear in the "lookForParent",
It violates rule #1 or #2, we can simply return false.
3. Its left and/or right node belongs to the list or appears in 'lookForParent".
(a) Remove this node from the list.
(b) Check if this node's child(ren) are in the list or in the "lookForParent" recursively
(if not, it violates rule #1 or #2 and return false) and remove the node from the list
or from the "lookForParent".
(c) Move this node to "lookForParent".
At the end if the "lookForParent" hashset contains one node (it is the root), return true. Otherwise return false (violates rule #3).
public boolean isValidTree(List<Node> list){
Set<Node> set = new HashSet<Node>(list);
HashSet<Node> lookForParent = new HashSet<Node>();
for(Node each:list){
if(set.contains(each){
if(each.left == null && each.right == null){
set.remove(each);
lookForParent.add(each);
}
else if(each.left != null || each.right != null){
Node tmp = each;
boolean good = checkChildren(each.left,set,lookForParent) &&
checkChildren(each.right,set,lookForParent);
if(good){
lookForParent.add(tmp);
}
else{
return false;
}
}
}
}
if(lookForParent.size() == 1){
return true;
}
return false;
}
public boolean checkChildren(Node node, HashSet<Node> set, HashSet<Node> lookForParent){
if(node == null) return true;
else if(lookForParent.contains(node)){
lookForParent.remove(node);
return true;
}
else if(set.contains(node)){
set.remove(node);
return checkChildren(each.left,set,lookForParent) &&
checkChildren(each.right,set,lookForParent);
}
return false;
}
public static boolean findAll(List<TreeNode> list){
if(list==null || list.size()<1){
return false;
}
Map<TreeNode,Integer> map = new HashMap<>();
for(TreeNode ele:list){
if(!map.containsKey(ele)){
map.put(ele,0);
}
if(ele.left!=null){
map.put(ele.left,map.getOrDefault(ele.left,0)+1);
}
if(ele.right!=null){
map.put(ele.right,map.getOrDefault(ele.right,0)+1);
}
}
TreeNode root = null;
for(TreeNode ele:list){
int val = map.get(ele);
if(val==0&&root!=null){
return false;
}else if(val==0 && root==null){
root=ele;
}else if(val>1){
return false;
}
}
preorderTree(root,map);
return map.size()==0;
}
public static void preorderTree(TreeNode root,Map<TreeNode,Integer> map){
if(root==null){
return;
}
preorderTree(root.left,map);
preorderTree(root.right,map);
map.remove(root);
}
public static boolean findAll(List<TreeNode> list){
if(list==null || list.size()<1){
return false;
}
Map<TreeNode,Integer> map = new HashMap<>();
for(TreeNode ele:list){
if(!map.containsKey(ele)){
map.put(ele,0);
}
if(ele.left!=null){
map.put(ele.left,map.getOrDefault(ele.left,0)+1);
}
if(ele.right!=null){
map.put(ele.right,map.getOrDefault(ele.right,0)+1);
}
}
TreeNode root = null;
for(TreeNode ele:list){
int val = map.get(ele);
if(val==0&&root!=null){
return false;
}else if(val==0 && root==null){
root=ele;
}else if(val>1){
return false;
}
}
preorderTree(root,map);
return map.size()==0;
}
public static void preorderTree(TreeNode root,Map<TreeNode,Integer> map){
if(root==null){
return;
}
preorderTree(root.left,map);
preorderTree(root.right,map);
map.remove(root);
}
- noob October 23, 2017