How to reverse a tree in C# the Functional way in 5 lines of code

source fiddle:https://dotnetfiddle.net/gtj8wA

Trees are the single most important data structure in computer science, after lists. Just about everything you do in your programming career will be related to trees. For example JSON objects, xml, html DOM are tree structures. C# developers when they enter the realm of functional programming quickly learn how to use Select , and Aggregate in order to replace traditional for loops on lists. What they do not learn is that Trees also have a map and reduce methods. In this article we are going to display the functional way to reverse a Binary Tree .

if we have a tree that look like this

     6
   /   \     
  3     4            
 / \   / \
7   3 8   1

we want to define a function Reverse that will give us as a result this tree

     6
   /   \
  4     3
 / \   / \
1   8 3   7

we are going to start Defining a Tree structure

Defining Pattern matching on Trees

The first thing we are going to define is a very simple matchWith method on the tree structure.

public class Node<T> : Tree<T>
    {
        public Tree<T> Left { get; set; }
        public T Value { get; set; }
        public Tree<T> Right { get; set; }

        public Node(Tree<T> left, T value, Tree<T> right)
        {
            this.Left = left;
            this.Value = value;
            this.Right = right;
        }
        public override T1 MatchWith<T1>((Func<T, T1> Leaf, Func<Tree<T>, T, Tree<T>, T1> Node) algebra)                                                                      => algebra.Node(Left, Value, Right);

    }

    public class Leaf<T> : Tree<T>
    {
        public T V { get; }
        public Leaf(T v) => V = v;
        public override T1 MatchWith<T1>((Func<T, T1> Leaf, Func<Tree<T>, T, Tree<T>, T1> Node) algebra) => algebra.Leaf(V);
    }

This takes as an argument an object:

.MatchWith(algebra: (
                Leaf: v => {...},
                Node: (l, v, r) => {...}  
            )

and allows us to distinguish between Node and Leaf[this is called pattern matching]

And that’s it !!!!! we are done. We can now define any type of recursive method on this tree. So how we are going to define Reverse recursively.

Take a look at the following Fiddle

all the magic happens here:

public static Tree<T> Reverse<T>(this Tree<T> @this) =>
  @this.MatchWith<Tree<T>>(algebra: (
   Leaf: v => new Leaf<T>(v),
   Node: (l, v, r) => new Node<T>(r.Reverse<T>(), v, l.Reverse<T>())
  ));

1. If you are on a leaf just return the leaf : Leaf: v => new Leaf<T>(v)

2. If you are on a node just call reverse on the Left and Right Nodes and then just return a node with those reversed new nodes : new Node<T>(r.Reverse<T>(), v, l.Reverse<T>())

[by the way this method of recursive definition is called structural induction]

Excerpt from Functional Programming in C#