How to write a recursive function that returns a linked list of nodes, when given a binary tree of nodes?

Question

I was once asked of this in an interview:

How to write a recursive function that returns a linked list of nodes, when given a binary tree of nodes? (flattening the data) (Update: how about, don't just traverse the tree and add the nodes to a global structure. Make the function totally recursive, and modifying the binary tree in place)

For some reason, I tend to need more than 3 to 5 minutes to solve any recursive problem. Usually, 15 to 20 minutes will be more like it. How could we attack this problem, such as a very systematic way of reaching a solution, so that they can be solved in 3 to 5 minute time frame?

Answer 1

How about "make linked lists of the two branches, then append one to the other"?

I don't think there exists a systematic method that will solve any recursive problem in less than 5 minutes. Sometimes the fractal nature of the problem is just too hard to find.

Answer 2

There are several ways you can traverse binary tree. For example, you can get children first, or you can get left children, then parent, then right children.

Assume you have class Node with fields value, leftChild and rightChild. Sample java code for leftchild-parent-rightchild traversal:

public List<Node> traverseTree (Node parentNode) {
   List<Node> nodes = new LinkedList<Node> ();
   if (parentNode.hasLeftChild ()) {
      nodes.addAll (traverseTree (parentNode.getLeftChild ()));
   }
   nodes.add (parentNode);
   if (parentNode.hasRightChild ()) {
      nodes.addAll (traverseTree (parentNode.getRightChild ()));
   }
   return nodes;
}

Answer 3

Like that

public class Tree
{
    public Tree Left { get; set; }
    public Tree Right { get; set; }

    public List<Tree> FlatTree()
    {
        var list = new List<Tree>();
        list.Add(this);
        if (Left!=null) list.AddRange(Left.FlatTree());
        if (Right!= null) list.AddRange(Right.FlatTree());
        return list;
    }
}

add itself, add left branch flatterned, add rightbranch flatterned

Answer 4

Pretty much what @vittore did, but with single list allocation (but it will get reallocated internally, so..). This is also probably (brain malfunctioning) in order.

public List<Tree> Flat(List<Tree> t)
{
    var t = t ?? new List<Tree>();
    Left != null ? Left.Flat(t):;        
    t.Add(this);        
    Right != null ? Right.Flat(t):;
    return t;
}