Most efficient way to generate all descendents of all nodes in a tree

Question

I'm looking for the most efficient algorithm to take a tree (stored as either a list of edges; OR as a list of mappings from parent node to a list of child nodes); and produce, for EVERY node, a list of all nodes descended from it (leaf level and non-leaf level).

The implementation must be via loops instead of recusion, due to scale; and should ideally be O(N).

This SO question covers a standard reasonably obvious solution for finding the answer for ONE node in a tree. But obviously, repeating that algorithm on every tree node is highly inefficient ( off the top of my head, O(NlogN) to O(N^2) ).

The tree root is known. The tree is of absolutely arbitrary shape (e.g. not N-nary, not balanced in any way, shape or form, not uniform depth) - some nodes have 1-2 children, some have 30K children.

On a practical level (though it shouldn't affect the algorithm) the tree has ~100K-200K nodes.

Answer 1

If you actually want to PRODUCE every list as different copies, you cannot hope to achieve better than n^2 space in the worst case. If you just need ACCESS to each list:

I would perform an in-order traversal of the tree starting from the root:

http://en.wikipedia.org/wiki/Tree_traversal

Then for each node in the tree store the minimum in-order number and maximum in-order number in its subtree (this is easily maintained through recursion -- and you can simulate that with a stack if you wish).

Now you put all nodes in an array A of length n where the node with in-order number i is in position i. Then when you need to find the list for a node X, you look in A[X.min, X.max] -- note that this interval will include the node X, which can also easily be fixed.

All of this is accomplished in O(n) time and takes O(n) space.

I hope this helps.

Answer 2

The inefficient part is not traversing the tree, but building the lists of nodes. It would seem sensible to create the list like this:

descendants[node] = []
for child in node.childs:
    descendants[node].push(child)
    for d in descendants[child]:
        descendants[node].push(d)

Since each descendant node is copied into the list of each parent, we end up with O(n log n) complexity on average for balanced trees, and O(n²) worst case for degenerate trees that are really linked lists.

We can drop to O(n) or O(1) depending on whether you need to do any setup if we use the trick of calculating the lists lazily. Assume we have a child_iterator(node) that gives us the childs of that node. We can then trivially define a descendant_iterator(node) like this:

def descendant_iterator(node):
  for child in child_iterator(node):
    yield from descendant_iterator(child)
  yield node

A non-recursive solution is much more involved, since iterator control flow is tricky (coroutines!). I'll update this answer later today.

Since traversal of a tree is O(n) and iteration over a list is linear as well, this trick completely defers the cost until it is paid anyway. For example, printing out the list of descendants for each node has O(n²) worst case complexity: Iterating over all nodes is O(n) and so is iterating over each node's descendants, whether they are stored in a list or calculated ad hoc.

Of course, this won't work if you need an actual collection to work on.

Answer 3

This short algorithm should do it, Have a look at the code public void TestTreeNodeChildrenListing()

The algorithm actually goes through the nodes of the tree in sequence, and keeping the list of parents of the current node. As per your requirement current node is a child of each parent node it's added to each and every one of them as a child.

Final result is stored in the dictionary.

    [TestFixture]
    public class TreeNodeChildrenListing
    {
        private TreeNode _root;

        [SetUp]
        public void SetUp()
        {
            _root = new TreeNode("root");
            int rootCount = 0;
            for (int i = 0; i < 2; i++)
            {
                int iCount = 0;
                var iNode = new TreeNode("i:" + i);
                _root.Children.Add(iNode);
                rootCount++;
                for (int j = 0; j < 2; j++)
                {
                    int jCount = 0;
                    var jNode = new TreeNode(iNode.Value + "_j:" + j);
                    iCount++;
                    rootCount++;
                    iNode.Children.Add(jNode);
                    for (int k = 0; k < 2; k++)
                    {
                        var kNode = new TreeNode(jNode.Value + "_k:" + k);
                        jNode.Children.Add(kNode);
                        iCount++;
                        rootCount++;
                        jCount++;

                    }
                    jNode.Value += " ChildCount:" + jCount;
                }
                iNode.Value += " ChildCount:" + iCount;
            }
            _root.Value += " ChildCount:" + rootCount;
        }

        [Test]
        public void TestTreeNodeChildrenListing()
        {
            var iteration = new Stack<TreeNode>();
            var parents = new List<TreeNode>();
            var dic = new Dictionary<TreeNode, IList<TreeNode>>();

            TreeNode node = _root;
            while (node != null)
            {
                if (node.Children.Count > 0)
                {
                    if (!dic.ContainsKey(node))
                        dic.Add(node,new List<TreeNode>());

                    parents.Add(node);
                    foreach (var child in node.Children)
                    {
                        foreach (var parent in parents)
                        {
                            dic[parent].Add(child);
                        }
                        iteration.Push(child);
                    }
                }

                if (iteration.Count > 0)
                    node = iteration.Pop();
                else
                    node = null;

                bool removeParents = true;
                while (removeParents)
                {
                    var lastParent = parents[parents.Count - 1];
                    if (!lastParent.Children.Contains(node)
                        && node != _root && lastParent != _root)
                    {
                        parents.Remove(lastParent);
                    }
                    else
                    {
                        removeParents = false;
                    }
                }
            }
        }
    }

    internal class TreeNode
    {
        private IList<TreeNode> _children;
        public string Value { get; set; }

        public TreeNode(string value)
        {
            _children = new List<TreeNode>();
            Value = value;
        }

        public IList<TreeNode> Children
        {
            get { return _children; }
        }
    }
}

Answer 4

Normally, you would just use a recursive approach, because it allows you to switch your execution order around such that you can calculate the number of leaves starting from the leaves upwards. Since, you would have to use the result of your recursive call to update the current node, it would take special effort to get a tail recursive version. If you do not take that effort, then of course, this approach would simply explode your stack for a large tree.

Given that we realized the main idea is to get a looping order starting at the leaves and going back up towards the root, the natural idea that comes to mind is to perform a topological sort on the tree. The resulting sequence of nodes can be traversed linearly in order to sum the number of leaves (assuming you can verify a node is a leaf in O(1)). The overall time complexity of the topological sort is O(|V|+|E|).

I assume that your N is the number of nodes, which would be |V| typically (from the DAG nomenclature). The size of E on the other hand highly depends on your tree's arity. For example, a binary tree has at most 2 edges per node, therefore O(|E|) = O(2*|V|) = O(|V|) in that case, which would result in an overall O(|V|) algorithm. Note that due to the overall structure of a tree, you cannot have something like O(|E|) = O(|V|^2). In fact, since each node has a unique parent, you can have at most one edge to count per node when you consider only parent-relations, so for trees we have a guarantee that O(|E|) = O(|V|). Therefore, the above algorithm is always linear in the size of the tree.