code: def prefix_tree(paths):
      """Creates a directed prefix tree from a list of paths.
  
      Usually the paths are described as strings or lists of integers.
  
      A "prefix tree" represents the prefix structure of the strings.
      Each node represents a prefix of some string. The root represents
      the empty prefix with children for the single letter prefixes which
      in turn have children for each double letter prefix starting with
      the single letter corresponding to the parent node, and so on.
  
      More generally the prefixes do not need to be strings. A prefix refers
      to the start of a sequence. The root has children for each one element
      prefix and they have children for each two element prefix that starts
      with the one element sequence of the parent, and so on.
  
      Note that this implementation uses integer nodes with an attribute.
      Each node has an attribute "source" whose value is the original element
      of the path to which this node corresponds. For example, suppose `paths`
      consists of one path: "can". Then the nodes `[1, 2, 3]` which represent
      this path have "source" values "c", "a" and "n".
  
      All the descendants of a node have a common prefix in the sequence/path
      associated with that node. From the returned tree, the prefix for each
      node can be constructed by traversing the tree up to the root and
      accumulating the "source" values along the way.
  
      The root node is always `0` and has "source" attribute `None`.
      The root is the only node with in-degree zero.
      The nil node is always `-1` and has "source" attribute `"NIL"`.
      The nil node is the only node with out-degree zero.
  
  
      Parameters
      ----------
      paths: iterable of paths
          An iterable of paths which are themselves sequences.
          Matching prefixes among these sequences are identified with
          nodes of the prefix tree. One leaf of the tree is associated
          with each path. (Identical paths are associated with the same
          leaf of the tree.)
  
  
      Returns
      -------
      tree: DiGraph
          A directed graph representing an arborescence consisting of the
          prefix tree generated by `paths`. Nodes are directed "downward",
          from parent to child. A special "synthetic" root node is added
          to be the parent of the first node in each path. A special
          "synthetic" leaf node, the "nil" node `-1`, is added to be the child
          of all nodes representing the last element in a path. (The
          addition of this nil node technically makes this not an
          arborescence but a directed acyclic graph; removing the nil node
          makes it an arborescence.)
  
  
      Notes
      -----
      The prefix tree is also known as a *trie*.
  
  
      Examples
      --------
      Create a prefix tree from a list of strings with common prefixes::
  
          >>> paths = ["ab", "abs", "ad"]
          >>> T = nx.prefix_tree(paths)
          >>> list(T.edges)
          [(0, 1), (1, 2), (1, 4), (2, -1), (2, 3), (3, -1), (4, -1)]
  
      The leaf nodes can be obtained as predecessors of the nil node::
  
          >>> root, NIL = 0, -1
          >>> list(T.predecessors(NIL))
          [2, 3, 4]
  
      To recover the original paths that generated the prefix tree,
      traverse up the tree from the node `-1` to the node `0`::
  
          >>> recovered = []
          >>> for v in T.predecessors(NIL):
          ...     prefix = ""
          ...     while v != root:
          ...         prefix = str(T.nodes[v]["source"]) + prefix
          ...         v = next(T.predecessors(v))  # only one predecessor
          ...     recovered.append(prefix)
          >>> sorted(recovered)
          ['ab', 'abs', 'ad']
      """
  
      def get_children(parent, paths):
          children = defaultdict(list)
          # Populate dictionary with key(s) as the child/children of the root and
          # value(s) as the remaining paths of the corresponding child/children
          for path in paths:
              # If path is empty, we add an edge to the NIL node.
              if not path:
                  tree.add_edge(parent, NIL)
                  continue
              child, *rest = path
              # `child` may exist as the head of more than one path in `paths`.
              children[child].append(rest)
          return children
  
      # Initialize the prefix tree with a root node and a nil node.
      tree = nx.DiGraph()
      root = 0
      tree.add_node(root, source=None)
      NIL = -1
      tree.add_node(NIL, source="NIL")
      children = get_children(root, paths)
      stack = [(root, iter(children.items()))]
      while stack:
          parent, remaining_children = stack[-1]
          try:
              child, remaining_paths = next(remaining_children)
          # Pop item off stack if there are no remaining children
          except StopIteration:
              stack.pop()
              continue
          # We relabel each child with an unused name.
          new_name = len(tree) - 1
          # The "source" node attribute stores the original node name.
          tree.add_node(new_name, source=child)
          tree.add_edge(parent, new_name)
          children = get_children(new_name, remaining_paths)
          stack.append((new_name, iter(children.items())))
  
      return tree
  
imports: import warnings
  from collections import Counter, defaultdict
  from math import comb, factorial
  import networkx
  from networkx.utils import py_random_state
label_desc: Use image node_id 1 for calling a global function with example usage: prefix_tree(paths) and returns: tree, children