O(N) tree branch cutting: a simple solution without BFS or DFS


  • 0
    N

    The idea is simple:
    Given a tree, we cut out all nodes whose degree is ONE. Thus, the root with minimum depth will be the one or two nodes left after iterations of cuts. This process looks pretty similar to pruning bush or peeling an onion. Here is an example:

    0  1  2                    
     \ | / 
       3 - 6 - 7       =>     4-3-6       = >    3
       |
       4
       |
       5
    
    

    My Python implementation is here:

            if n < 3:   return [i for i in range(n)]
            # Build Adjacent list
            d = {i: set() for i in range(n)}
            for e in edges:
                d[e[1]].add(e[0])
                d[e[0]].add(e[1])
            # Iteratively aggregate degree 1 node
            cur = {i for i in range(n) if len(d[i]) == 1}
            left = {i for i in range(n) if i not in cur}
            while len(left) > 2:
                related = [(list(d[i])[0], i) for i in cur]
                for key, val in related:
                    d[key].discard(val)
                cur = {i for i in left if len(d[i]) == 1}
                left = left - cur
            return list(left)
    

Log in to reply
 

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