# Generate a binary tree from parent->child relationship

Given a list of child->parent relationships, build a binary tree out of it. All the element Ids inside the tree are unique.

Example:

Given the following relationships:

Child Parent IsLeft
15 20 true
19 80 true
17 20 false
16 80 false
80 50 false
50 null false
20 50 true

You should return the following tree:

``````    50
/  \
20   80
/ \   / \
15 17 19 16
``````

Function Signature

``````/**
* Represents a pair relation between one parent node and one child node inside a binary tree
* If the _parent is null, it represents the ROOT node
*/
class Relation {
int parent;
int child;
bool isLeft;
};

/**
* Represents a single Node inside a binary tree
*/
class Node {
int id;
Node * left;
Node * right;
}

/**
* Implement a method to build a tree from a list of parent-child relationships
* And return the root Node of the tree
*/
Node * buildTree (vector<Relation> & data)
{
}
``````

• ``````class Node {
public Node(int id) {
this. id = id;
}
int id;
Node  left;
Node  right;
}

Node buildTree ()
{
Map<Integer, Node> tree = new HashMap<>();

try {
Node root  =  null;
String str  =  null;
while ((str = br.readLine()) != null) {
String[] array  =  str.split(" ");
Node parent  =  null;
if  (!array[1].equals("null")) {
parent  =  tree.get(Integer.parseInt(array[1]));
if (parent  ==  null) {
int a  =  Integer.parseInt(array[1]);
tree.put(a, new Node(a));
parent  =  tree.get(a);
}
}

int a = Integer.parseInt(array[0]);
Node child = tree.get(a);

if (child == null) {
tree.put(a, new Node(a));
child = tree.get(a);
}
if (parent == null)
root = child;
else {
if (array[2].equals("true")) {
parent.left = child;
} else {
parent.right = child;
}
}
}

}
catch(IOException exc) {
exc.printStackTrace();
}
finally {
if (br != null)
try {
br.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return root;
}``````

• Python solution:

``````class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

f = open('file', 'r')
arr = []
nodes = []
for line in f:
arr.append(line.split())

f.close()

def preOrder(root):
if not root:
return
print root.val
preOrder(root.left)
preOrder(root.right)

def createBin(arr):
root = None
for i in arr:
i[0] = int(i[0])
try:
i[1] = int(i[1])
except ValueError:
pass
if type(i[1]) is str and i[1] == 'null':
if not i[0] in [j.val for j in nodes]:
n = Node(i[0])
root = n
nodes.append(n)
else:
for j in nodes:
if j.val == i[0]:
root = j
break
continue

if not i[1] in [j.val for j in nodes]:
n = Node(i[1])
nodes.append(n)
if not i[0] in [j.val for j in nodes]:
n1 = Node(i[0])
nodes.append(n1)

for n in nodes:
if n.val == i[1]:
for n1 in nodes:
if n1.val == i[0]:
if i[2] == 'true':
n.left = n1
else:
n.right = n1

return root
``````

preOrder(createBin(arr))

• From this one more question can be formed. Given relationships, determine root?

• ``````public class TreeBuilder<T>
{
private readonly IDictionary<T, Node<T>> cache = new Dictionary<T, Node<T>>();

public TreeBuilder(IEnumerable<Relation> relations)
{
this.relations = relations;
}

public Node<T> Build()
{
cache.Clear();

Node<T> root = null;

foreach (var relation in relations)
{
Node<T> parentNode = null;
bool isRoot = relation.Parent.Equals(default(T));

if (isRoot)
{
cache.TryGetValue(relation.Child, out parentNode);

if (parentNode == null)
{
parentNode = new Node<T>(relation.Child);
cache[ relation.Child ] = parentNode;
}

root = parentNode;

continue;
}

cache.TryGetValue(relation.Parent, out parentNode);

if (parentNode == null)
{
parentNode = new Node<T>(relation.Parent);
cache[ relation.Parent ] = parentNode;
}

Node <T> childNode;

cache.TryGetValue(relation.Child, out childNode);

if (childNode == null)
{
parentNode.Relate(relation.Child, relation.IsLeft);
}
else
{
parentNode.Relate(childNode, relation.IsLeft);
}
}

return root;
}

public enum Status : short
{
Left,
Right,
Root
};

public class Relation
{
public Relation(T parent, T child) : this(parent, child, Status.Right)
{
}

public Relation(T parent, T child, Status status)
{
Parent = parent;
Child = child;
Status = status;
}

public T Parent { get; private set; }
public T Child { get; private set; }
public Status Status { get; private set; }

public bool IsLeft
{
get
{
return Status.Equals(Status.Left);
}
}

public bool IsRoot
{
get
{
return Status.Equals(Status.Root);
}
}

public override string ToString()
{
return \$"({Parent},{Child},{Status})";
}
};
}
``````

`Node<T>`

``````public class Node<T>
{
public Node(T value)
{
Id = DateTime.Now.Ticks;
Value = value;
}

public long Id { get; private set; }
public T Value { get; private set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }

public override string ToString()
{
var left = Left?.Value.ToString();
var right = Right?.Value.ToString();

return \$"({Value})[{left}, {right}]";
}

public void Relate(Node<T> child, bool left)
{
if (left)
{
Left = child;
}
else
{
Right = child;
}
}

public void Relate(T childValue, bool left)
{
if (left)
{
if (Left == null)
{
Left = new Node<T>(childValue);
}
else
{
Left.Value = childValue;
}

return;
}

if (Right == null)
{
Right = new Node<T>(childValue);
}
else
{
Right.Value = childValue;
}
}

public static void PreOrderTraverse(Node<T> root, Action<Node<T>, TreeBuilder<T>.Status> action, Object internalDoNotUse = null)
{
if (root == null)
{
return;
}

action(root, (TreeBuilder<T>.Status) (internalDoNotUse ?? TreeBuilder<T>.Status.Root));
PreOrderTraverse(root.Left, action, TreeBuilder<T>.Status.Left);
PreOrderTraverse(root.Right, action, TreeBuilder<T>.Status.Right);
}
}
``````

Testing `TreeBuilder`

``````var relations = new TreeBuilder<int>.Relation[]
{
new TreeBuilder<int>.Relation(20, 15, TreeBuilder<int>.Status.Left),
new TreeBuilder<int>.Relation(80, 19, TreeBuilder<int>.Status.Left),
new TreeBuilder<int>.Relation(20, 17),
new TreeBuilder<int>.Relation(80, 16),
new TreeBuilder<int>.Relation(50, 80),
new TreeBuilder<int>.Relation(0, 50, TreeBuilder<int>.Status.Root),
new TreeBuilder<int>.Relation(50, 20, TreeBuilder<int>.Status.Left),
};

var builder = new TreeBuilder<int>(relations);
var root = builder.Build();

Console.WriteLine(\$"Root --> \${root}");

Node<int>.PreOrderTraverse(root, (n, s) => {
var sign = s == TreeBuilder<int>.Status.Left
? "<"
: (s == TreeBuilder<int>.Status.Right ? ">" : "*");

Console.WriteLine(\$"{sign}{n.Value}");
});

``````

• Code

``````import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

public class GenerateBinaryTree {

public static class Relation {
public Integer parent, child;
public boolean isLeft;

public Relation(Integer parent, Integer child, boolean isLeft) {
this.parent = parent;
this.child = child;
this.isLeft = isLeft;
}
}

public static class Node {
public Integer val;
public Node left, right;

public Node(Integer val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}

private static HashMap<Integer, Node> mapOfNodes;

public static Node buildTree(List<Relation> relations) {
mapOfNodes = new HashMap<Integer, Node>();

Iterator<Relation> relationsIterator = relations.iterator();
Relation relation;
Node root = null;

while (relationsIterator.hasNext()) {
Node parentNode, childNode;
relation = relationsIterator.next();

if (relation.parent == null) {
root = getChildNode(relation.child);
continue;
}

if (mapOfNodes.containsKey((relation.parent))) {
parentNode = mapOfNodes.get(relation.parent);
childNode = getChildNode(relation.child);
if (relation.isLeft)
parentNode.left = childNode;
else
parentNode.right = childNode;
} else {
childNode = getChildNode(relation.child);
parentNode = new Node(relation.parent, relation.isLeft ? childNode : null, relation.isLeft ? null : childNode);
mapOfNodes.put(relation.parent, parentNode);
}
}

return root;
}

private static Node getChildNode(Integer child) {
Node childNode;
if (mapOfNodes.containsKey((child))) {
childNode = mapOfNodes.get(child);
} else {
childNode = new Node(child, null, null);
mapOfNodes.put(child, childNode);
}
return childNode;
}
}
``````

Some Unit Tests

``````import static org.junit.Assert.*;

import java.util.ArrayList;

import org.junit.Test;

import GenerateBinaryTree.Node;
import GenerateBinaryTree.Relation;

public class GenerateBinaryTreeTest {

private static ArrayList<Relation> generateRelation(String relationsString) {
ArrayList<Relation> relations = new ArrayList<Relation>();

if (relationsString == null || relationsString.length() == 0)
return relations;

for (String relationString : relationsString.split(":")) {
String[] tempSplit = relationString.split(",");
Relation relation = new Relation(tempSplit[1].equals("null") ? null : new Integer(tempSplit[1]), new Integer(tempSplit[0]), Boolean.parseBoolean(tempSplit[2]));
}

return relations;
}

private static ArrayList<Integer> nodeList;

private static String convertTree(Node root) {
nodeList = new ArrayList<Integer>();
convertTreeHelper(root);
return nodeList.toString();
}

private static void convertTreeHelper(Node node) {
if (node == null)
return;
convertTreeHelper(node.left);
convertTreeHelper(node.right);
}

@Test
public void test1() {
ArrayList<Relation> relations = generateRelation("15,20,true:19,80,true:17,20,false:16,80,false:80,50,false:50,null,false:20,50,true");
Node root = GenerateBinaryTree.buildTree(relations);
assertEquals(convertTree(root), "[15, 20, 17, 50, 19, 80, 16]");
}

@Test
public void test2() {
ArrayList<Relation> relations = generateRelation("50,null,false:20,50,true");
Node root = GenerateBinaryTree.buildTree(relations);
assertEquals(convertTree(root), "[20, 50]");
}

@Test
public void test3() {
ArrayList<Relation> relations = generateRelation("50,null,false:20,50,false");
Node root = GenerateBinaryTree.buildTree(relations);
assertEquals(convertTree(root), "[50, 20]");
}

@Test
public void test4() {
ArrayList<Relation> relations = generateRelation("50,null,false");
Node root = GenerateBinaryTree.buildTree(relations);
assertEquals(convertTree(root), "[50]");
}

@Test
public void test5() {
ArrayList<Relation> relations = generateRelation("50,null,true");
Node root = GenerateBinaryTree.buildTree(relations);
assertEquals(convertTree(root), "[50]");
}

@Test
public void test6() {
ArrayList<Relation> relations = generateRelation("");
Node root = GenerateBinaryTree.buildTree(relations);
assertEquals(convertTree(root), "[]");
}

}
``````

• ``````dic = dict()
for relation in relations:
val,pval,left = relation
if val not in dic:
node = Node(val)
dic[val] = node
if pval is None:
root = node
continue
if pval not in dic:
parent = Node(pval)
dic[val] = parent
if left:
parent.left = node
else:
parent.right = node
return root``````

• ``````public static TreeNode buildTree(List<Relation> relations) {
TreeNode root = null;
Map<Integer, TreeNode> map = new HashMap<Integer,TreeNode>();
for(Relation relation: relations){
if(relation.parent==null) {//we met root node
if(!map.containsKey(relation.child)) map.put(relation.child, new TreeNode(relation.child));
root = map.get(relation.child);
}
else if(relation.child==null){//we met leave node
if(!map.containsKey(relation.parent)) map.put(relation.parent, new TreeNode(relation.parent));
}
else{
if(!map.containsKey(relation.parent)&&!map.containsKey(relation.child)){
TreeNode parentNode = new TreeNode(relation.parent);
TreeNode childNode = new TreeNode(relation.child);
if(relation.isLeft) parentNode.left = childNode;
else parentNode.right = childNode;
map.put(relation.parent, parentNode);
map.put(relation.child, childNode);
}
else if(map.containsKey(relation.parent)&&map.containsKey(relation.child)){
if(relation.isLeft) map.get(relation.parent).left = map.get(relation.child);
else map.get(relation.parent).right = map.get(relation.child);
}
else if(map.containsKey(relation.parent))	{
TreeNode childNode = new TreeNode(relation.child);
map.put(relation.child, childNode);
if(relation.isLeft) map.get(relation.parent).left = childNode;
else map.get(relation.parent).right = childNode;
}
else{
TreeNode parentNode = new TreeNode(relation.parent);
map.put(relation.parent, parentNode);
if(relation.isLeft) parentNode.left = map.get(relation.child);
else parentNode.right = map.get(relation.child);
}
}

}
return root;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.