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


  • 1
    C

    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


  • 0

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


  • 0
    C

    sorry about that.


  • 0

    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?


  • 0
    C

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

    TreeNode {

      int val;
     TreeNode right, left;
    

    }


  • 3
    L

    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

  • 0
    J

    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
    }


  • 0

    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();
    }
    

  • 0

    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.


Log in to reply
 

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