Filter a tree using recursion

Question

I have a tree that appears as follows.

A1
  B1
    B2   
    A2
      A3 
      B3
        A4        
  A5
  C1
    C2
      C3
        A6

I want to filter this to return

A1
  A2
    A3 
    A4        
  A5
  A6

The basic idea is to only return A nodes. The struggle that I am having is in the case A2 I want to drop B1 and pull A2 up to the level of B2

I am using c# The tree is made up of List of Nodes

Answer 1

You want to to a depth search (recursion) and eliminate nodes which aren't A's, right?

I'd remove the nodes on the way back, inserting the children to the parent (at the position of the node you're currently on) and then remove this node whenever you are on a non-A node.

Something like this (simplified pseudo-code, you have to be careful with changing node collections while they are being iterated etc.):

void FilterNode(Node node) {
    foreach (Node child in node.Children) {
        FilterNode(child);
    }
    if (node.Type != NodeType.A) {
        foreach (Node child in node.Children) {
            node.Parent.InsertAfter(node, child);
        }
        node.Parent.RemoveNode(node);
    }
}

Answer 2

I'm going to assume your tree structure looks like this:

class Node<T> {
    public readonly T Value;
    public readonly LinkedList<Node<T>> Children;
    public readonly bool IsEmtpy;

    public Node() {
        IsEmpty = true;
    }

    public Node(T value, LinkedList<Node<T>> children) {
        Value = value;
        Children = children;
        IsEmpty = false;
    }
}

You can filter your tree in a single pass with a single depth first search.

I usually find it easier to prototype these sorts of algorithms in a functional language, then translate them to C# when needed. Here's the F# code:

type 'a tree = Nil | Node of 'a * 'a tree list

// val filter : ('a -> bool) -> 'a tree list -> 'a tree list
let rec filter f = function
    | Node(value, children)::xs ->
        if f value then Node(value, filter f children)::filter f xs
        else (filter f children) @ filter f xs
    | Nil::xs -> filter f xs
    | [] -> []

let input =
    Node("A1",
        [ Node("B1",
            [ Node("B2", []);
              Node("A2",
                [ Node("A3", []);
                  Node("B3", [ Node("A4", []) ]) ]) ]);
          Node("A5", []);
          Node("C1",
            [ Node("C2",
                [Node("C3", [ Node("A6", []) ]) ]) ]) ])

let expectedOutput =
    Node("A1",
        [ Node("A2",
            [ Node("A3", []);
              Node("A4", []) ]);
          Node("A5", []);
          Node("A6", []) ])

let actualOutput = [input] |> filter (fun value -> value.StartsWith("A")) |> List.head

let testPasses = expectedOutput = actualOutput

And the F# output:

val testPasses : bool = true

And here's the equivalent code in C#:

static LinkedList<Node<T>> Filter(Func<T, bool> predicate, IEnumerable<Node<T>> input) {
    var res = new LinkedList<Node<T>>();

    foreach(Node<T> node in input) {
        if (!node.IsEmpty) {
            if (predicate(node.Value)) {
                res.AddLast(new Node(node.Value, Filter(predicate, node.Children));
            else {
                res.AddRange(Filter(predicate, node.Children));
            }
        }
    }

    return res;
}