How to filter trees recursively: Golang, JavaScript, and PHP examples

Filtering tree graphs is one of the most popular (and sometimes challenging) tasks developers face. So, here I decided to provide a couple of examples with some solutions.

In simple words, trees are graphs in which you have only one path from the root to some specific branch. Every branch can be connected to the next child branches. Please see an example of a simple tree:

As you can see, it is possible to access branch “8” only if you go this path: “1–2–5–8”.

Now you may ask and what is so challenging with trees? :D

The thing is that when you filter a simple list you don’t have to check if every item on this list is connecting to other lists, you just remove items that do not correspond with filter params.

Let’s think about an example. Please take a look at the tree above and try to catch how it should look if we remove branches which numbers are not prime. It means that branches “5, 7, 3, 9, 1” have to disappear. But is that correct?
If we remove 1, then all trees will disappear, since 1 is a root. Also, we 5 or 3 will be removed, 8 and 6 will also be removed, but these numbers should be in the tree.

So, if the child branch corresponds to the filter condition, we should keep the parent branch in a tree.

How to solve it?

So, to solve this you have two basic options:
1) Move all branches on the same level, mark parents for every child branch, filter branches as a simple list, and build a tree again.
2) Go recursively to every branch and if some branch is not corresponded with the filter condition remove it.

I like nature so I wouldn’t recommend destroying the trees :D

But as a developer, I also may say, that the first option is not so fast as the second one since you need to do two redundant actions: destroy and rebuild the tree.

So, let’s proceed with the second option.

What is the algorithm?

Probably you are curious about when we finally start coding? :) Then I have good news, this time has come!
Let’s take a look at the algorithm briefly:
1) Check if the branch has applied with filter conditions, if yes, return true;
2) Check child branches if they correspond with filter condition and remove which is not.
3) Repeat that process, until all branches are checked.

I promised you the examples, now here it is:

1) GoLang: https://github.com/OleksiiFedorchak/filter-trees-recursively/blob/master/filter.go
2) JavaScript: https://github.com/OleksiiFedorchak/filter-trees-recursively/blob/master/filter.js
3) PHP: https://github.com/OleksiiFedorchak/filter-trees-recursively/blob/master/filter.php

A few words about the code…

The idea is to separate check specific branches and a list of branches. For checking specific branch, responsible filterCallback(). This function returns a bool. Based on this we can judge should we keep a branch in the tree, or it has to be removed.

Function filter() go recursively into every branch and call filterCallback() on every branch.

Please take a note: these examples don’t contain global variables, which typically are used in the recursive functions to keep progress. But since global variables are not a good pattern at all, I wouldn’t recommend to use them ;)

The idea separation filterCallback() and filter() make this code reusable. To implement this in practice, you may just change a condition in your filterCallback() and don’t touch another part of the code.

I hope this article was useful! If you can any comments or questions please contact me via my email: ofedorchak68@gmail.com, or via my LinkedIn account: https://www.linkedin.com/in/oleksii-fedorchak-3bab3361/