Finding the left-most child for every node in a tree in linear time?

Question

A paper I am reading claims that

It is easy to see that there is a linear time algorithm to compute the function l()

where l() gives the left-most child (both input and output are in postorder traversal of the tree). However, I can only think of a naive O(n^2) implementation where n is the number of nodes in the tree.

As an example, consider the following tree:

  a
 / \
c   b

In postorder traversal, the tree is c b a. The corresponding function l() should give c b c.

Here is my implementation in O(n^2) time.

public Object[] computeFunctionL(){
    ArrayList<String> l= new ArrayList<String>();
    l= l(this, l);
    return l.toArray();
}

private ArrayList<String> l(Node currentRoot, ArrayList<String> l){
    for (int i= 0; i < currentRoot.children.size(); i++){
        l= l(currentRoot.children.get(i), l);
    }
    while(currentRoot.children.size() != 0){
        currentRoot= currentRoot.children.get(0);
    }
    l.add(currentRoot.label);
    return l;
}

The tree is made as:

public class Node {
private String label;
private ArrayList<Node> children= new ArrayList<Node>();
...

Answer 1

There is a simple recursive algorithm you can use that can compute this information in O(1) time per node. Since there are n total nodes, this would run in O(n) total time.

The basic idea is the following recursive insight:

• For any node n with no left child, l(n) = n.
• Otherwise, if n has left child L, then l(n) = l(L).

This gives rise to this recursive algorithm, which annotates each node with its l value:

function computeL(node n) {
   if n is null, return.

   computeL(n.left)
   computeL(n.right)

   if n has no left child:
      set n.l = n
   else
      set n.l = n.left.l

Hope this helps!

Answer 2

You can find l() for the entire tree in less than O(n^2) time. The idea is to traverse the tree in order, maintaing a stack of the nodes you've visited while traversing the left branch. When you get to a leaf, that is the leftmost node for the entire branch.

Here's an example:

class BTreeNode
{
    public readonly int Value;
    public BTreeNode LeftChild { get; private set; }
    public BTreeNode RightChild { get; private set; }
}

void ShowLeftmost(BTreeNode node, Stack<int> stack)
{
    if (node.LeftChild == null)
    {
        // this is the leftmost node of every node on the stack
        while (stack.Count > 0)
        {
            var v = stack.Pop();
            Console.WriteLine("Leftmost node of {0} is {1}", v, node.Value);
        }
    }
    else
    {
        // push this value onto the stack so that
        // we can add its leftmost node when we find it.
        stack.Push(node.Value);
        ShowLeftmost(node.LeftChild, stack);
    }
    if (node.RightChild != null)
        ShowLeftmost(node.RightChild, stack);
}

The complexity is clearly not O(n^2). Rather, it's O(n).

It takes O(n) to traverse the tree. No node is placed on the stack more than once. The worst case for this algorithm is a tree that contains all left nodes. In that case it's O(n) to traverse the tree and O(n) to enumerate the stack. The best case is a tree that contains all right nodes, in which case there is never any stack to enumerate.

So O(n) time complexity, with O(n) worst case extra space for the stack.

Answer 3

Take a look at section 3.1:

3.1. Notation. Let T[i] be the ith node in the tree according to the left-to-right postorder numbering, l(i) is the number of the leftmost leaf descendant of the subtree rooted at T[i].

Given that sentence about notation, I would assume that the function l() is referring to finding a single node in linear time.

There may be a more elegant (better than O(n^2)) way of finding l() for an entire tree but I think it's referring to a single node.