How to Solve any Binary Tree Problem
With Functional Programming
Functional Programming and Binary Trees are both challenging topics engineers face on the job and during their interviews.
Now we don’t actually cover functional programming as part of our curriculum at Outco, even though it’s an awesome subject. But we do cover trees and graphs a fair bit.
And since I use callbacks a lot as a Javascript engineer, one day I got curious about whether I could put both concepts together.
But on the surface, the two topics seem completely unrelated.
Functional Programming, on the one hand, is very abstract because requires you to bend your mind when thinking about functions as either arguments or return values to other functions. But the benefit of using functional programming is that you end up writing less code, and the code you do write is usually more readable (declarative), despite the initial steep learning curve.
Binary Trees, on the other hand, require you to think non-linearly because they are a branched data structure and in reverse because to traverse a binary tree means often means using recursion going depth first. But the benefit of knowing about binary trees (and trees in general), besides helping you pass interviews, is that they are all around you as an engineer. Your file system is a tree, database lookups can be made more efficient with trees, and they are often just a good way of modeling information and relationships.
The question I’m going to explore with this post is can both concepts be used together? And what, if any benefit is there in mixing the two?
So in other words “will they blend?”
Here’s what I found down the rabbit hole…
It all started when I noticed that a lot of our solutions to binary tree problems that we give engineers look very similar.
Whether we were trying to invert the tree, or print the values of all the nodes, or find the maximum height of the tree, or count the number of nodes in the tree, all the coded ended up looking very similar.
And the main reason for this is because we usually did some kind of depth first search, while performing an operation on whatever node we were on at the time.
Note: In all these examples you don’t have a tree class, the root node is just passed in as the argument. Here is the node class we’ll be using:
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}Let’s look at the code for the above problems with the operation we’re performing in bold.
Here’s what the code for inverting a binary tree looks like:
function invertTree(root) { function dfs(node) { if(node === null) return; [node.left, node.right] = [node.right, node.left]; dfs(node.left);
dfs(node.right);
}
dfs(root);
}
Here’s the code for printing every value of the tree:
function printTree(root) { function dfs(node) { if(node === null) return; console.log(node.val); dfs(node.left);
dfs(node.right);
}
dfs(root);
}
Here’s the code for calculating the maximum depth of a tree:
function height(root) { function dfs(node) { if(node === null) return 0; return Math.max(dfs(node.left), dfs(node.right)) + 1;
} dfs(root);
}
And here’s the code for counting the nodes in a tree:
function countNodes(root) { function dfs(node) { if(node === null) return 0; return dfs(node.left) + dfs(node.right) + 1;
} dfs(root);
}
The solution code is so similar between these examples, that even in writing this post, I copied and pasted from one to the other with a few modifications. And as a general rule, any time you are copying and pasting code there’s probably a better to do whatever it is you’re trying to do.
The key insight came to me when I realized we could decouple the logic for traversing the tree, and the logic for the operation we were performing on each node.
The inspiration came from when I was originally learned about functional programming in the context of arrays. Here’s a great resource for that: Eloquent JavaScript.
JavaScript has a built in forEach method on arrays, that allows you to apply some function to every element in the array. This abstracts away the boiler plate code of traversing the array, incrementing some counter, and setting an end condition. So printing goes from this:
let arr = [1, 2, 3, 4, 5];for(let i = 0; i < arr.length; i++){
console.log(arr[i]);
}
To this:
let arr = [1, 2, 3, 4, 5];arr.forEach(console.log)
Or slightly more spelled out:
arr.forEach(element => {
console.log(element)
}Now you longer need to be thinking about the traversal of the array, just what needs to happen to every element in the array.
This is a subtle improvement, but it’s a powerful one.
Let’s take a look at what forEach looks like on the inside by defining our own forEach function:
function forEach(array, callback) { for(let i = 0; i < array.length; i++) { callback(array[i], i)
}
}
This callback argument could be any function we want, and whatever that function is, it will have access to both element arr[i] and the index i itself as its first and second arguments.
And just to reiterate, the main thing this achieves is decoupling the logic for iterating over this linear array, with the logic of performing operations on each element in it.
So how would this decoupling look on a binary tree class?
Let’s take a look…
First we need a tree class:
class BST {
constructor() {
this.root = null;
}
addNode(val) {
function dfs(node) {
if(node === null) {
return new TreeNode(val);
}
if(val >= node.val) {
node.right = dfs(node.right);
} else {
node.left = dfs(node.left);
}
return node;
}
this.root = dfs(this.root);
}addNodes(arr) {
let tree = this;
arr.forEach(val => {
tree.addNode(val);
})
}
}
This is nothing fancy. It just creates a basic Binary Search Tree class, and allows you to add a bunch of nodes at once with the addNodes method.
So our example tree will be:
let tree = new BST()
tree.addNodes([40, 20, 60, 10, 30, 50, 70])/*
40
/ \
20 60
/ \ / \
10 30 50 70*/
Now let’s write a forEachNode method that will apply a callback to every node on the tree:
forEachNode(callback) {
function dfs(node) {
if(node === null) return null;
callback(node);
dfs(node.left);
dfs(node.right);
return node;
}
dfs(this.root);
return this;
}This code looks very similar to all the other traversal code we had been writing. It performs a dfs over the whole tree except now, the operation we are doing is abstract. It’s just an argument called callback we pass into the forEachNode method.
So now we can define those functions like print and invert outside of the tree class.
function print(node) {
console.log(node.val);
}function invert(node) {
[node.left, node.right] = [node.right, node.left];
}
These are really simple functions that only need to know what to do on a single node. The forEach handles the logic of applying that function to every node in the tree.
One last key thing to notice, is that forEach returns a reference to this , meaning we can chain calls to forEach , allowing us to do multiple things in sequence to the tree:
tree.forEachNode(print).forEachNode(invert).forEachNode(print);And that’s all there is to it!
This got me thinking about what other higher order functions I could write for binary trees.
The next most obvious one to me was “reduce”. But this one was quite a bit harder for me to wrap my head around and figure out how to apply it to a binary tree. After spending a few hours banging my head against the wall, trying all kinds of permutations of code, I gave up and decided to go home.
And while on the freeway on my drive back I had my Eureka moment.
As soon as I got home I coded it out and it worked on my first try!
For reference, here is the code for reduce applied to an array:
function reduce(array, reducer, startVal) { //Assumes Start Value let accumulator = start; for(let i = 0; i < array.length; i++) {
accumulator = reducer(current, arr[i]);
} return accumulator;
}
And this is what reduce looks like as a method on the BST class:
reduce(reducer, startVal) { //Assumes Start Value function dfs(node, accumulator) { if(node === null) return accumulator; return reducer(node,
dfs(node.left, accumulator),
dfs(node.right, accumulator));
}
return dfs(this.root, startVal);
}
Look at that code! Isn’t it beautiful?
There’s actually a term for this higher-order function. It’s essentially “reduce”, but applied to branched data structures. It’s called “fold”, and you can think of it like you’re folding up the tree (or graph) according to some rules.
So for example, if you were trying to add up all the values in a binary tree you would be “folding” up the values in tree until you had your final result. Or if you were searching for the height or width of the tree.
It’s like you’re condensing all the information according to a certain pattern.
But now that we have this function we can do all kinds of things with it. Let’s declare some outside helper functions:
// Reduce Functionsfunction height(node, left, right) {
return Math.max(left, right) + 1;
}function count(node, left, right) {
return 1 + left + right;
}function sum(node, left, right) {
return node.val + left + right;
}function leftWidth(node, left, right) {
return Math.min(left - 1, right + 1);
}function rightWidth( node, left, right) {
return Math.max(left - 1, right + 1);
}
And now we can add some methods to our tree class that use reduce, and the methods we just defined:
countNodes() {
return this.reduce(count, 0)
}sumTreeNodes() {
return this.reduce(sum, 0)
}height() {
return this.reduce(height, 0)
}width() {
return this.reduce(rightWidth, 0) - this.reduce(leftWidth, 0) -1
}
And that’s how you apply functional programming to binary trees!
I had a lot of fun writing these functions and then sharing the story of how I pushed my understanding of trees and functional programming. The next project I’m looking forward to trying my hand at is doing the same thing but with graphs now, so stay tuned for that post.
And I attached the original code below if anyone is interested.
Feel free to message or comment if you have questions, feedback or suggestions. I’m always looking to grow as a programmer and help others to do the same :).
And if you’re a software engineer on the job search looking to speed up that process don’t hesitate to reach out to use at Outco.io.
Happy coding!
