Generate a binary tree from parent->child relationship


  • 0
    M

    This was asked in LinkedIn Interview
    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)
    {
    }
    

  • 0
    class Node {
        public Node(int id) {
            this. id = id;
        }
        int id;
        Node  left;
        Node  right;   
    }
    
    Node buildTree ()
    {
        Map<Integer, Node> tree = new HashMap<>();
        BufferedReader br  = null;
        
        try {
            br  =  new BufferedReader(new FileReader("input"));    
            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;
    }

  • 0
    J

    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))


  • 0

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


  • 0
    V
    public class TreeBuilder<T>
    	{
    		private readonly IEnumerable<Relation> relations;
    		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}");
    			});
    
    

  • 0
    M

    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]));
    			relations.add(relation);
    		}
    
    		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);
    		nodeList.add(node.val);
    		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), "[]");
    	}
    
    }
    

  • 0
    S
    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

  • 0
    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;
    }

Log in to reply
 

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