8

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.

5

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.

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.

  • Sorry, -1. The whole purpose of the aglorithm is precomputing the data. Lazy computation is wholly defeating the reason for even running the algo. – DVK Jan 21 '15 at 17:22
  • 2
    @DVK Ok, I may have misunderstood your requirements. What are you doing with the resulting lists? If precomputing the lists is a bottleneck (but not using the lists), this would indicate you're not using all the data you aggregate, and lazy computation would then be a win. But if you use all data, the algorithm for precomputing is largely irrelevant – the algorithmic complexity of using the data will at least equal the complexity of building the lists. – amon Jan 21 '15 at 17:42
0

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; }
        }
    }
}
  • To me, this looks very much like O(n log n) to O(n²) complexity, and it improves only marginally over the answer that DVK linked to in their question. So if this is no improvement, how does this answer the question? The only value this answer adds is showcasing an iterative expression of the naive algorithm. – amon Jan 21 '15 at 9:15
  • It's O(n), If you look at the algorithm closely, it iterates once over the nodes. At the same time it creates the collection of child nodes for each parent node at the same time. – Low Flying Pelican Jan 21 '15 at 12:24
  • 1
    You loop through all nodes, which is O(n). Then you loop through all childs, which we'll ignore for now (let's imagine it's some constant factor). Then you loop through all parents of the current node. In a balances tree, this is O(log n), but in the degenerate case where our tree is a linked list, it may be O(n). So if we multiply the cost of looping through all nodes with the cost of looping through their parents, we get O(n log n) to O(n²) time complexity. Without multithreading, there is no “at the same time“. – amon Jan 21 '15 at 13:24
  • "at the same time" means it creates the collection in the same loop and there is no other loops involved. – Low Flying Pelican Jan 21 '15 at 13:38
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.