filter tree

Filter tree so that a node is skipped based on some condition and node's descendants become nearest ancestor's children.

input:
1
    2
    x
        x
            3a
                4
            3b

output:
1
    2
    3a
        4
    3b

to-include(node):
    // returns true or false on some condition
    returns true

node structure

node:
    string name
    node[] children

Keep a nearest ancestor pointer (initially null) and add current node to its children.

filteredTree = filter-tree(tree, null)

filter-tree(node, ancestor):
    if to-include(node):
        nodeCopy = new node(node.name)
        if ancestor != null:
            ancestor.children.add(nodeCopy)
        ancestor = nodeCopy
    foreach child in node.children:
        childAncestor = filter-tree(child, ancestor)
        if ancestor == null:
            ancestor = childAncestor
    return ancestor

The root node itself could be skipped, so the very first filtered node becomes root of filtered tree. There are cases where the hierarchy is not maintained.

input:
x
    x
        3a
            4
        3b

output:
3a
    4
    3b

input:
x
    x
        1
    x
        2

output:
1
    2

Another way is have a placeholder ancestor initially but the output tree will be different.

(node):
    nplaceholder = new 
    (node, nplaceholder)
    return nplaceholder.children
(node, ancestor):
    if to-include(node):
        ancestor.children.add(node)
        ancestor = node
    for child in node.children:
        (child, ancestor)