dimitris papadimitriou
dimitris papadimitriou More than 12 years’ experience as full stack developer and Software Architect . Functional javascript with categories.

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

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

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. Object oriented JavaScript developers when they enter the realm of functional programming quickly learn how to use map, and reduce in order to replace traditional for loops. 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

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

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

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

we are going to start from a ES6 Tree structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Tree {}

class Node extends Tree {
    constructor(left, v, right) {
        super()
        this.v = v;
        this.left = left;
        this.right = right;
    }
}

class Leaf extends Tree {
    constructor(v) {
        super()
        this.v = v;
    }
}

now we can represent the first Tree with an objects like this:

1
2
3
4
5
    6
   /   \     
  3     4            
 / \   / \
7   3 8   1
1
new Node(new Node(new Leaf(7),3,new Leaf(3)), 6, new Node(new Leaf(8),4,new Leaf(1)));

Defining Pattern matching on Trees

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Tree {}
class Node extends Tree {
    constructor(left, v, right) {
        super()
        this.v = v;
        this.left = left;
        this.right = right;
    }
    matchWith( pattern) {
        return  pattern.Node(this.left, this.v, this.right);
    }
}
class Leaf extends Tree {
    constructor(v) {
        super()
        this.v = v;
    }
    matchWith( pattern) {
        return  pattern.Leaf(this.v);
    } 
}

This takes as an argument an object:

1
2
3
4
pattern =({
     Leaf: v => {}   ,
     Node: (left, v, right) => { }
 })

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:

1
2
3
4
5
6
7
8
Tree.prototype.reverse = function ( ) {
    return this.matchWith({
        Leaf: v => new Leaf(v)   ,
        Node: (left, v, right) => {
            return new Node(right.reverse(),v,left.reverse())
        }
    });
}
  1. If you are on a leaf just return the leaf :Leaf: v => new Leaf(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(right.reverse(), v, left.reverse())

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

Lets do another example just so you can recognize the pattern.

Counting Nodes

Lets say we want to count the Nodes of the tree . how we are going to do this:

  1. if you are on a leaf just return 1
  2. if you are in a node just call countNodes on the Left and Right Nodes. and then sum the results (also the value node counts as +1).
1
2
3
4
5
6
7
8
Tree.prototype.countNodes = function() {
  return this.matchWith({
    Leaf: v => 1,
    Node: (left, v, right) => left.countNodes() 
                              + 1 
                              + right.countNodes()
  });
}

Conclusion:

Hopefully you are now ready to write recursive definitions on any tree by only using Cata. And i am not even kidding. Using functional definitions on Data structures will set you apart from the Rest of the pack.


Excerpt from the Book Functional Programming in Javascript in LeanPub https://leanpub.com/functional-programming-in-js-with-categories

comments powered by Disqus