CareerCup

package com.test;

import java.util.ArrayList;
import java.util.List;

public class TreeAsAMatrix {
    public static void main(String[] args) {
        boolean[][] adj = buildAdjacenyMatrix();
        TreeNode tree = buildTree(adj);
        printTree(tree);
    }

    private static boolean[][] buildAdjacenyMatrix() {
        boolean[][] matrix = new boolean[6][];
        //                                           0      1      2      3      4      5
        matrix[0] = new boolean[] { false, true , true , true , true , true  };
        matrix[1] = new boolean[] { false, false, false, false, false, false };
        matrix[2] = new boolean[] { false, false, false, false, false, false };
        matrix[3] = new boolean[] { false, false, false, false, false, false };
        matrix[4] = new boolean[] { false, false, false, false, false, false };
        matrix[5] = new boolean[] { false, false, false, false, false, false };

        return matrix;
    }

    private static TreeNode buildTree(boolean[][] adj) {
        TreeNode[] nodes = new TreeNode[adj.length];
        boolean[] hasParent = new boolean[adj.length];
        for(int i=0; i < adj.length; i++) {
            for(int j=0; j < adj.length; j++) {
                if (adj[i][j]) {
                    if (nodes[i] == null)
                        nodes[i] = new TreeNode(i);
                    if (nodes[j] == null)
                        nodes[j] = new TreeNode(j);
                    nodes[i].children.add(nodes[j]);
                    hasParent[j] = true;
                }
            }
        }

        for(int i=0; i < hasParent.length; i++)
            if(nodes[i] != null && !hasParent[i])
                return nodes[i];

        return null;
    }

    private static void printTree(TreeNode root) {
        if(root == null)
            System.out.println("Tree is empty");
        else
            printNode(root, "");
    }

    private static void printNode(TreeNode node, String prefix) {
        System.out.println(prefix + " -> " + node.data);
        for(TreeNode child : node.children)
            printNode(child, prefix + "   ");
    }

    private static class TreeNode {
        int data;
        List<TreeNode> children = new ArrayList<TreeNode>();
        TreeNode(int data) {
            this.data = data;
        }
    }

}

We can say , the Adjancy matrix representation of the graph is given , You have to create the tree from given 2D matrix.

I would have some other question as well to the Interviewer such as-
1- Graph is also a kind of tree , Printing a graph is answer? If yes then I will use BFS to print it.
If No.
2- How many child a tree can maximum have ?
Lets say 2
Then i will have to do following things-
1- Find the root Node from the graph, we can get the root by traversing the matrix and put every child in the set . One node must not be part of that set. That will be root.
2- Once we got the root... We can create a node in tree with root value.
3- Start DFS from root node and insert every node one by one.

We have to use DFS here because it will be easy to pass the parent as well with child to the calling function.

Node class for tree

class Node {
	int val;
	Node left, right;

	public Node(int val) {
		this.val = val;
	}
}

public Node dfs(Node parent, int child, boolean visited[],int[][] G) {
		Node temp = new Node(child);
		visited[child] = true;

		if (parent.left == null) {
			parent.left = temp;
		}else {
			parent.right = temp;
		}
		int n = G.length;
		for(int j=0;j<n;j++)
            if(!visited[j] && G[child][j]==1)
                dfs(temp,j,visited,G);
		return parent ;
	}

package main

import "fmt"

type Node struct {
	Value    int
	Children []*Node
}

func PrintTree(root *Node) {
	fmt.Print(root.Value, " -> {")
	for _, node := range root.Children {
		fmt.Print(node.Value, " ")
	}
	fmt.Println("}")
	for _, node := range root.Children {
		PrintTree(node)
	}
}

func MakeTree(matrix [][]bool) *Node {
	nodes := make([]*Node, len(matrix))
	hasParent := make([]bool, len(matrix))
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix); j++ {
			if matrix[i][j] {
				if nodes[i] == nil {
					nodes[i] = &Node{i, []*Node{}}
				}
				if nodes[j] == nil {
					nodes[j] = &Node{j, []*Node{}}
				}
				nodes[i].Children = append(nodes[i].Children, nodes[j])
				hasParent[j] = true
			}
		}
	}
	for i := 0; i < len(hasParent); i++ {
		if !hasParent[i] {
			return nodes[i]
		}
	}
	return nil
}

func main() {
	matrix := make([][]bool, 6)
	matrix[0] = []bool{false, true, true, true, false, false}
	matrix[1] = []bool{false, false, false, false, false, false}
	matrix[2] = []bool{false, false, false, false, true, true}
	matrix[3] = []bool{false, false, false, false, false, false}
	matrix[4] = []bool{false, false, false, false, false, false}
	matrix[5] = []bool{false, false, false, false, false, false}
	PrintTree(MakeTree(matrix))
}

//Node number and list of childrens it has.
HashMap<Integer,ArrayList<Integer>> hm = new HashMap();


//Will be used to find root
boolean is_child_of_someone[n+1];

rows = n;
cols = n;
for(i<rows)
{
for(j<cols)
{
//If j is child of i
if(mat[i][j] == 1)
{
if(!hm.containsKey(i))
hm.put(i,new ArrayList());

hm.get(i).add(j);

//as j is child of i
is_child_of_someone[j] = true;
}
}
}

int root=-1;


//Finding root
for( i<n )
{
if(!is_child_of_someone[i])
{
root = i;
break;
}
}

//Node number and list of childrens it has.
HashMap<Integer,ArrayList<Integer>> hm = new HashMap();


//Will be used to find root
boolean is_child_of_someone[n+1];

rows = n;
cols = n;
for(i<rows)
{
	for(j<cols)
    {
    	//If j is child of i
    	if(mat[i][j] == 1)
        {
        	if(!hm.containsKey(i))
                 hm.put(i,new ArrayList());

            hm.get(i).add(j);

            //as j is child of i
            is_child_of_someone[j] = true;
        }
	}
}

int root=-1;


//Finding root
for( i<n )
{
	if(!is_child_of_someone[i])
    {
    	root = i;
    	break;
    }
}

import java.util.*;
public class MatrixToTree
{
	public static void main(String args[])
	{
		int[][] mat = {{0, 1, 0, 0, 0},
						{0, 0, 1, 0, 0},
						{0, 0, 0, 1, 0},
						{0, 0, 0, 0, 1},
						{0, 0, 0, 0, 0}};
		MatrixToTree  m = new MatrixToTree();
		TreeNode root = m.create(mat);
		m.print(root);

	}

	public TreeNode create(int[][] mat)
	{
		Map<Integer, TreeNode> map = new HashMap<>();

		for(int i=0;i<mat.length;i++)
		{
			for(int j=0;j<mat[i].length;j++)
			{
				if(mat[i][j]==1)
				{
					helper(i, j, map);
				}
			}
		}

		int root = findRoot(mat);
		return map.get(root);
	} 


	private void helper(int p, int c, Map<Integer, TreeNode> map)	
	{
		TreeNode parent = map.getOrDefault(p, new TreeNode(p));
		TreeNode child = map.getOrDefault(c, new TreeNode(c));

		parent.children.add(child);
		map.put(p, parent);
		map.put(c, child);
	}


	private int findRoot(int[][] mat)
	{
		for(int col = 0; col<mat[0].length; col++)
		{
			boolean isRoot = true;
			for(int row = 0; row<mat.length; row++)
			{
				if(mat[row][col]==1)
				{
					isRoot = false;
					break;
				}
			}
			if(isRoot)
				return col;
		}
		return -1;
	}

	private void print(TreeNode root)
	{	
		Queue<TreeNode> next = new LinkedList<>();
		Queue<TreeNode> curr = null;
		next.offer(root);

		while(!next.isEmpty())
		{
			curr = next;
			next = new LinkedList<>();

			while(!curr.isEmpty())
			{
				TreeNode temp = curr.poll();
				System.out.print(temp.val+"\t");
				for(TreeNode child: temp.children)
				{
					next.offer(child);
				}
			}
			System.out.println();
		}
	}
}


class TreeNode
{
	int val;
	List<TreeNode> children;

	TreeNode(int val)
	{
		this.val= val;
		children = new ArrayList<>();
	}

	public String toString()
	{
		return val+ ": "+children;
	}
}