Linkedin Interview Question Testing / Quality Assurances
Country: United States
Interview Type: Phone Interview
One simple approach to this problem can be: we know the ROOT of the tree is the one where the parent is null in the list. Once we figure out the parent, we can iteratively figure out its children and their children- by looping over the complete list and finding out the ones that point the current node as its parent. To build tree efficiently, we can use queue to keep track of the tree built till then. The running time would be O(n^2), with constant space (not really, we are keeping a queue as well)
public static Node buildTree(List<Relation> data){
if(data==null) return new Node();
Node root=new Node();
int children=0;
for(int i=0;i<data.size();i++){
Relation x=data.get(i);
if(x.parent==null){
root=new Node(x.child,null,null);
break;
}
}
if(root==null) return root;
Queue<Node> q=new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
Node x=q.poll();
for(int i=0;i<data.size();i++){
Relation y=data.get(i);
if(y.parent==x.id){
Node n=new Node(y.child,null,null);
if(y.isLeft)
x.left=n;
else x.right=n;
q.add(n);
children++;
if(children==2){
children=0;
break;
}
}
}
}
return root;
}
Another way to approach this problem for a better running time could be by using a HashMap. We can hash the list with key as the parent and value as a list of its children. And then iteratively generating the tree. This solution would be O(n) time complexity and O(n) space complexity.
public static Node buildTree(List<Relation> data){
if(data==null) return new Node();
Node root=new Node();
HashMap<Integer,ArrayList<Relation>> tree = new HashMap<Integer,ArrayList<Relation>>();
for(Relation d:data){
if(d.parent==null)
root=new Node(d.child,null,null);
else{
if(tree.containsKey(d.parent)){
ArrayList<Relation> value=tree.get(d.parent);
value.add(d);
} else {
ArrayList<Relation> value = new ArrayList<Relation>();
value.add(d);
tree.put(d.parent,value);
}
}
}
if(root==null) return root;
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
Node x = q.poll();
if(tree.containsKey(x.id)){
ArrayList<Relation> value=tree.get(x.id);
for(Relation v:value){
Node child = new Node(v.child,null,null);
q.add(child);
if(v.isLeft)
x.left=child;
else x.right=child;
}
}
}
return root;
}
public static Node buildTree(List<Relation> data) {
if (data == null || data.isEmpty()) {
return null;
}
Node root = null;
Map<Integer, Node> mapNode = new HashMap<Integer, Node>();
for (Relation relation : data) {
if (relation.parent == null) {
if (mapNode.containsKey(relation.child)) {
root = mapNode.get(relation.child);
} else {
root = new Node(relation.child);
mapNode.put(root.val, root);
}
continue;
}
Node parent;
if (mapNode.containsKey(relation.parent)) {
parent = mapNode.get(relation.parent);
addChild(mapNode, relation, parent);
} else {
parent = new Node(relation.parent);
mapNode.put(parent.val, parent);
addChild(mapNode, relation, parent);
}
}
return root;
}
private static void addChild(Map<Integer, Node> mapNode, Relation relation, Node parent) {
Node childNode = mapNode.containsKey(relation.child) ? mapNode.get(relation.child) : new Node(relation.child);
if (relation.isLeft) {
parent.left = childNode;
} else {
parent.right = childNode;
}
mapNode.put(childNode.val, childNode);
}
We know the head will have a null parent. Now that we have a head, we will know the 2nd level of the tree will be the nodes that have the head as a parent, so organize the tree by how those nodes are organized.
You can keep a queue- put 50 into it first, then search the list for nodes that attach to 50. add those to the queue. dequeue 50. search the list for nodes that attach to the nodes in the queue, add to the queue and dequeue the lists you found nodes for. continue this process until both the list and the queue are empty.
Some very loose pseudocode:
buildTree(list) {
Node head;
Queue treeQueue = ;// initializeQueue
for (info in list) {
head = node who's parent is null;
}
list.remove(head);
treeQueue.enqueue(head);
Node current;
while(list != empty) {
current = treeQueue.dequeue();
for (node in list) {
if (node's parent is current) {
enqueue(node);
if (node.isLeft) { current.left = node;} else { current.right = node}
}
}
}
return head;
}
Here is a C# solution written as an xUnit test. Idea is to iterate once over the relations and then keep all Nodes in a dictionary and then stitch them together as we iterate over the relations.
using System.Collections.Generic;
using System.Diagnostics;
using Xunit;
namespace CareerCupSolutions {
public class BinaryTree_20150318 {
public class Relation {
public Relation(int child, int parent, bool isLeft) {
Parent = parent;
Child = child;
IsLeft = isLeft;
}
public int Parent { get; private set; }
public int Child { get; private set; }
public bool IsLeft { get; private set; }
}
public class Node {
public Node(int id, Node left, Node right) {
Id = id;
Left = left;
Right = right;
}
public int Id { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
public Node BuildTree(List<Relation> data) {
var _nodes = new Dictionary<int, Node>();
Node root = null;
foreach (var relation in data) {
Node parentNode;
Node childNode;
if (!_nodes.TryGetValue(relation.Parent, out parentNode)) _nodes[relation.Parent] = parentNode = new Node(relation.Parent, null, null);
if (!_nodes.TryGetValue(relation.Child, out childNode)) _nodes[relation.Child] = childNode = new Node(relation.Child, null, null); ;
if (relation.IsLeft) {
Debug.Assert(parentNode.Left == null);
parentNode.Left = childNode;
}
else {
Debug.Assert(parentNode.Right == null);
parentNode.Right = childNode;
}
if (relation.Parent == 0) root = _nodes[relation.Child];
}
return root;
}
[Fact]
public void Test() {
var list = new List<Relation> {
new Relation(15, 20, true),
new Relation(19, 80, true),
new Relation(17, 20, false),
new Relation(16, 80, false),
new Relation(80, 50, false),
new Relation(50, 0, false),
new Relation(20, 50, true),
};
var root = BuildTree(list);
Assert.Equal(50, root.Id);
Assert.Equal(20, root.Left.Id);
Assert.Equal(80, root.Right.Id);
Assert.Equal(15, root.Left.Left.Id);
Assert.Equal(17, root.Left.Right.Id);
Assert.Equal(19, root.Right.Left.Id);
Assert.Equal(16, root.Right.Right.Id);
}
}
}
Here is a C# solution as an xUnit test which iterate over the relations, keeps nodes in a dictinary and stitches them together according to the relations:
using System.Collections.Generic;
using System.Diagnostics;
using Xunit;
namespace CareerCupSolutions {
public class BinaryTree_20150318 {
public class Relation {
public Relation(int child, int parent, bool isLeft) {
Parent = parent;
Child = child;
IsLeft = isLeft;
}
public int Parent { get; private set; }
public int Child { get; private set; }
public bool IsLeft { get; private set; }
}
public class Node {
public Node(int id, Node left, Node right) {
Id = id;
Left = left;
Right = right;
}
public int Id { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
public Node BuildTree(List<Relation> data) {
var _nodes = new Dictionary<int, Node>();
Node root = null;
foreach (var relation in data) {
Node parentNode;
Node childNode;
if (!_nodes.TryGetValue(relation.Parent, out parentNode)) _nodes[relation.Parent] = parentNode = new Node(relation.Parent, null, null);
if (!_nodes.TryGetValue(relation.Child, out childNode)) _nodes[relation.Child] = childNode = new Node(relation.Child, null, null); ;
if (relation.IsLeft) {
Debug.Assert(parentNode.Left == null);
parentNode.Left = childNode;
}
else {
Debug.Assert(parentNode.Right == null);
parentNode.Right = childNode;
}
if (relation.Parent == 0) root = _nodes[relation.Child];
}
return root;
}
[Fact]
public void Test() {
var list = new List<Relation> {
new Relation(15, 20, true),
new Relation(19, 80, true),
new Relation(17, 20, false),
new Relation(16, 80, false),
new Relation(80, 50, false),
new Relation(50, 0, false),
new Relation(20, 50, true),
};
var root = BuildTree(list);
Assert.Equal(50, root.Id);
Assert.Equal(20, root.Left.Id);
Assert.Equal(80, root.Right.Id);
Assert.Equal(15, root.Left.Left.Id);
Assert.Equal(17, root.Left.Right.Id);
Assert.Equal(19, root.Right.Left.Id);
Assert.Equal(16, root.Right.Right.Id);
}
}
}
Each node is either a left child or a right child. Make two hashmaps, one for lefts and one for rights; key is the parent id, and value is the child id.
Figure out which one the head is while you're adding all of the relations (O(n)). Then, starting with the head, do a DFS with the help of a stack and figure out the children accordingly!
public LINode buildTree(List<Relation> data) {
HashMap<Integer, Integer> leftMap = new HashMap<>();
HashMap<Integer, Integer> rightMap = new HashMap<>();
LINode head = new LINode();
for (Relation i:data) {
if (i._isLeft) {
leftMap.put(i._parent, i._child);
} else {
rightMap.put(i._parent, i._child);
}
if (i._parent==null) head._id = i._child;
}
java.util.Stack<LINode> stack = new Stack<>();
stack.push(head);
while (!stack.empty()) {
LINode tracker = stack.pop();
if (rightMap.containsKey(tracker._id)) {
tracker._right = new LINode();
tracker._right._id = rightMap.get(tracker._id);
stack.push(tracker._right);
}
if (leftMap.containsKey(tracker._id)) {
tracker._left = new LINode();
tracker._left._id = leftMap.get(tracker._id);
stack.push(tracker._left);
}
}
return head;
}
"""
20: [15, None]
15: [None, 7]
7: [1, 2]
1: [None, None]
2: [None, None]
Root => 20
"""
def print_tree(node):
if node is not None:
print_tree(node.left)
print node.value
print_tree(node.right)
def get_binary_tree():
data = [
(50, None, False),
(15, 50, False),
]
parent_to_children_map = {}
root = None
for (child, parent, is_left) in data:
if parent is None:
root = child
else:
if parent not in parent_to_children_map:
parent_to_children_map[parent] = [None, None]
if is_left:
parent_to_children_map[parent][0] = child
else:
parent_to_children_map[parent][1] = child
tree = create_tree(root, parent_to_children_map)
print_tree(tree)
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def create_tree(node_id, parent_to_children_map):
if node_id is None:
return None
if node_id not in parent_to_children_map:
return Node(node_id)
n = Node(node_id)
[left_id, right_id] = parent_to_children_map[node_id]
n.left = create_tree(left_id, parent_to_children_map)
n.right = create_tree(right_id, parent_to_children_map)
return n
get_binary_tree()
public static Node buildTree(List<Relation> data)
{
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
Node root = null;
for(Relation r: data) {
Node parent, child;
if ((child = map.get(r.child)) == null) {
System.out.println("Here");
child = new Node();
child.data = r.child;
map.put(r.child, child);
}
if (r.parent == 0) {
root = child;
continue;
}
if ((parent = map.get(r.parent)) == null) {
parent = new Node();
parent.data = r.parent;
map.put(r.parent, parent);
}
if (r.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}
Here is C++ version of solution.
I used HashTable to store and search the node that had been created.
Running time is O(M), where M is number of relationships.
Assumption is that HashTable is real hash table.
Give the implementation I used std::map which gives O(logn) search time.
I would implement HashTable to get O(1) search time if time is allowed.
Space complexity is O(N), where N is number of nodes.
Node * buildTree(Relation * data, int len)
{
Node * root = 0;
map<int, Node*> nodemap;
for (int i = 0; i < len; i++)
{
Node * p = 0;
Node * c = 0;
int pid = data[i].parent;
int cid = data[i].child;
if (pid != INT_MIN)
{
if (nodemap.find(pid) != nodemap.end())
{
p = nodemap[pid];
} else {
p = new Node(pid);
nodemap[pid] = p;
}
}
if (nodemap.find(cid) != nodemap.end())
{
c = nodemap[cid];
} else {
c = new Node(cid);
nodemap[cid] = c;
}
if (pid == INT_MIN)
{
root = c;
}
if (p) {
if (data.isLeft)
p->left = c;
else
p->right = c;
}
}
return root;
}
private Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
public Node buildTree (List<Relation> data) {
Node root = null;
for (Relation relation : data) {
//parent exists
Node parent;
Node child;
if (relation != null && relation.child != null) {
if (nodeMap.get(relation.child) != null) {
child = nodeMap.get(relation.child);
} else {
child = new Node(relation.child, null, null);
nodeMap.put(relation.child, child);
}
if (relation.parent == null) {
root = child;
} else {
if (nodeMap.get(relation.parent) != null) {
parent = nodeMap.get(relation.parent);
} else {
parent = new Node(relation.parent, null, null);
nodeMap.put(relation.parent, parent);
}
if (relation.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
}
}
return root;
}
private Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
public Node buildTree (List<Relation> data) {
Node root = null;
for (Relation relation : data) {
//parent exists
Node parent;
Node child;
if (relation != null && relation.child != null) {
if (nodeMap.get(relation.child) != null) {
child = nodeMap.get(relation.child);
} else {
child = new Node(relation.child, null, null);
nodeMap.put(relation.child, child);
}
if (relation.parent == null) {
root = child;
} else {
if (nodeMap.get(relation.parent) != null) {
parent = nodeMap.get(relation.parent);
} else {
parent = new Node(relation.parent, null, null);
nodeMap.put(relation.parent, parent);
}
if (relation.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
}
}
return root;
}
public static TreeNode<Integer> buildTree(final List<Relation> data) {
Map<Integer, TreeNode<Integer>> hashMap = new HashMap<>();
TreeNode<Integer> root = null;
for (final Relation r : data) {
TreeNode<Integer> parent = hashMap.containsKey(r._parent) ? hashMap.get(r._parent) : new TreeNode<>(r._parent);
hashMap.put(r._parent, parent);
TreeNode<Integer> child = hashMap.containsKey(r._child) ? hashMap.get(r._child) : new TreeNode<>(r._child);
hashMap.put(r._child, child);
if (r._parent == null) {
root = child;
continue;
}
if (r._isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}
public static TreeNode<Integer> buildTree(final List<Relation> data) {
Map<Integer, TreeNode<Integer>> hashMap = new HashMap<>();
TreeNode<Integer> root = null;
for (final Relation r : data) {
TreeNode<Integer> parent = hashMap.containsKey(r._parent) ? hashMap.get(r._parent) : new TreeNode<>(r._parent);
hashMap.put(r._parent, parent);
TreeNode<Integer> child = hashMap.containsKey(r._child) ? hashMap.get(r._child) : new TreeNode<>(r._child);
hashMap.put(r._child, child);
if (r._parent == null) {
root = child;
continue;
}
if (r._isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}
public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
graph.get(curr._parent).add(curr);
}
Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}
private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);
if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;
}
public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
graph.get(curr._parent).add(curr);
}
Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}
private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);
if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;
}
public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
graph.get(curr._parent).add(curr);
}
Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}
private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);
if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;
}
public static void buildTree(Iterable<Relation> tree)
{
Map<Integer, List<Relation>> graph = new HashMap<>();
Iterator<Relation> rel = tree.iterator();
Relation root = null;
while(rel.hasNext()) {
Relation curr = (Relation) rel.next();
if(curr._parent == null) {
root = curr;
continue;
}
graph.putIfAbsent(curr._parent, new ArrayList<Relation>());
graph.get(curr._parent).add(curr);
}
Node mainRoot = buildTree(root._child, graph);
inorder(mainRoot);
}
private static Node buildTree(int root, Map<Integer, List<Relation>> graph) {
Node newNode = new Node(root);
if(graph.get(root) != null) {
for(Relation r : graph.get(root)) {
if(r._isLeft)
newNode._left = buildTree(r._child, graph);
else
newNode._right = buildTree(r._child, graph);
}
}
return newNode;
}
O(n) solution using a map [O(n) memory]
- AP August 05, 2015public Node buildTree(List<Relation> data)
{
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
Node root = null;
for(Relation r: data) {
Node parent, child;
if ((child = map.get(r.child)) == null) {
System.out.println("Here");
child = new Node();
child.data = r.child;
map.put(r.child, child);
}
if (r.parent == 0) {
root = child;
continue;
}
if ((parent = map.get(r.parent)) == null) {
parent = new Node();
parent.data = r.parent;
map.put(r.parent, parent);
}
if (r.isLeft) {
parent.left = child;
} else {
parent.right = child;
}
}
return root;
}