# Find the root of a binary tree in a list of tree nodes

• 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

• Quick question, how come node `H` is not present in the input list?

• No worries, also just want to clarify the data structure of the tree node, does each node have a parent pointer that points to the parent node?

• No , they do not have that information. They have a regular TreeNode information, like

TreeNode {

``````  int val;
TreeNode right, left;
``````

}

• 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.

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