Given list of nodes of a tree, find the root of the tree. Nodes in the list are not in any particular order. If some of the nodes in the tree are not given, return null
Eg:
A
B C
E F
Input : [B, C, A, E, F] Output : A
What you can do is iterate through the list of nodes and check each node's left and right.
Make a copy of the node list and remove a node if it is a left node or right node during the iteration of the node list.
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def isRoot(node_list):
nodes = set(node_list)
for node in node_list:
if node.left is not None:
nodes.remove(node.left)
if node.right is not None:
nodes.remove(node.right)
return nodes.pop() if len(nodes) == 1 else None
type tree struct {
key int
left, right *tree
}
var treeNodeList []*tree
func returnRootNodesfromlist(tlist []*tree) *tree {
//Built Map ;
copyLMap := make(map[*tree]bool, 0)
//Call copy in-built function
for _, n := range tlist {
copyLMap[n] = true
}
//till hear , built-up Map
//Now Walk to list and remove node right and left node from MAp
for _, n := range tlist {
if n.left != nil {
delete(copyLMap, n.left)
}
if n.right != nil {
delete(copyLMap, n.right)
}
}
if len(copyLMap) > 0 {
for _, n := range copyLMap {
return n
}
}
return nil
}
Use a poor man's topological sort by deleting all child nodes from the list. The remaining element is clearly the root. Here we use a set to ensure that the remove
operation is swift:
public TreeNode findRoot(List<TreeNode> list) {
Set<TreeNode> set = new HashSet<>(list);
for(TreeNode node : list) {
if (node.left != null) set.remove(node.left);
if (node.right != null) set.remove(node.right);
}
return set.iterator().next();
}
Umm.. bear with me here, I might be terribly wrong.
Why not just go through the list of nodes and try and find the node which never figures in either *left
or *right
of any other node? That node is most definitely the root.
If you are left with multiple nodes that satisfy the above, then the information on the tree is probably incomplete or it's an unresolvable situation. In which case we return null
, just like the question demands.
EDIT: Looks like @schumpeter suggested the same thing.