Breadth-First Search in Typescript and Javascript

I have been coding in Typescript for some time and I love it. It’s incredible of just how similar it is to iOS Swift. They have a lot of syntactic similarities except from, Typescript does have a bit of Java in it i.e. the semicolons. The reason I mention Swift is because I have been coding in Swift longer than Typescript. Regardless, at the end of the day, they are programming languages and if you know one you can easily pick up another. Also, unlike my first love Java, they are both less verbose and I do appreciate most of it (not sure about “fat arrows”). If you like, you can have a look at my post on implementing breadth first search in Swift. In this post, I will talk about how to implement the breadth first search in Typescript. This blogpost will be short on the text but heavy on the code samples. This post will be like the first version of my post, I aim to update it later with improvements. I will be providing Typescript code samples for the following,

1. Queue data structure
2. TreeNode of Binary Tree
3. Binary Search Tree
   1. and a method for level order traversal

Hence, let’s get started on the post, but first…

Stack or Queue?

I have always preferred the Stack data structure over a queue, hence I find it ironic, I am talking about breadth-first search (BFS). I mean, as opposed to Depth-First Search which uses a stack. I love Stack, way way more than a Queue, it’s one of my favourite data structures of all time. Not sure if it’s the FILO, the visualisation of FILO in my mind or my love for the “undo” operation? Something about it clearly appeals to me way more than a Queue.

Breadth-First Search in Typescript

Or level order traversal, the two terms pretty much refer to the same thing. The time I use level order traversal is when I defining the pre-order, post-order and in-order traversals. If you do a search for BFS on either Google or Bing, you can find an article that explains it well. For this post, let’s look at the Typescript code.

Queue<T> class

/*
A queue that can be of type T
Generics are great in any language
*/
class Queue<T> {
    private items: T[] = [];
    /* Add and pop do the same thing
    One has the fat arrow syntax
    */
    public add = (item: T) => this.items.push(item);

    public pop(): T {
        return this.items.shift();
    }

    isEmpty():boolean {
        return this.items.length == 0;
    }
}

The add and pop methods! why do they look different? They are both methods but one uses the ES6 “Fat Arrow” syntax and the other one’s more traditional. The “Fat Arrow” or Arrow Functions were introduced in ES6 and it makes the code a lot less verbose. I am not fully convinced by it! why? While it certainly makes the code less verbose, it does make it harder to read for new comers. Hence, at this stage, I reckon it maybe less maintainable.

TreeNode<T>

class TreeNode<T> {
    private key: T;
    private leftChild?: TreeNode<T>;
    private rightChild?: TreeNode<T>;

    constructor(key: T) {
        this.key = key;
    }
    getKey = ():T => this.key; 
    //just to practice the fat arrow function
    getLeftChild = ():TreeNode<T> => this.leftChild;

    getRightChild(): TreeNode<T> {
        return this.rightChild;
    }
    setLeftChild = (leftNode: TreeNode<T>) => this.leftChild = leftNode;

    setRightChild(rightChild: TreeNode<T>) {
        this.rightChild = rightChild;
    }
}

The above code is self explanatory except the use of optionals for leftChild and rightChild. I love Optionals!! They are the best. Ohh my god, the amount of times, I have been frustrated with null pointer exceptions in Java! Declaring a property as optional means it can be a null value in it’s life time. I first used optionals in iOS Swift and initially it seemed a bit strange but soon it made sense. Can you see how optionals are used here? A node in a tree, may or may not have left or right nodes, hence the declared as such private leftChild?: TreeNode<T>; Note the question mark at the end of leftChild.  once again do note my use of Fat Arrow function. I would love to know what you guys think of the Fat Arrow functions? Do you agree with me, that they make it less readable and maintainable? or you think it’s the way to do things and it’s very easy to pick up for anyone? I admit, it did take me all of 5-10 minutes to understand it and start using it. I personally love it but I am concerned about the time it takes a junior programmer who’s maintaining it to come to terms with it. A few years ago, this would not be a concern for me at all. However, in the last few years of running my startup and trying to mentor juniors, I realised, I took a lot of things for granted.

Get updates?

Leave this field empty if you're human:

p.s. Declaring optionals in Swift is the same, except in Swift, the question mark would be at the end of the type and without semi-colon i.e. private leftChild: TreeNode<T>?

BinaryTree<H>

/*
let's just traverse everything from
the root node
*/
class BinaryTree<H> {
    private rootNode: TreeNode<H>;

    setRoot = (node: TreeNode<H>) => this.rootNode = node;

    public addNode(key: H): void {
        this.rootNode = this.addNodeByRecursion(this.rootNode, key);
    }
    public addNodeByRecursion(currentNode: TreeNode<H>, key: H): TreeNode<H> {
        if (currentNode == null) {
            return new TreeNode<H> (key);
        }
        if (key < currentNode.getKey()) {
            currentNode.setLeftChild(this.addNodeByRecursion(currentNode.getLeftChild(), key));
        } else if(key > currentNode.getKey()) {
            currentNode.setRightChild(this.addNodeByRecursion(currentNode.getRightChild(), key));
        }
        return currentNode;
    }
    public levelOrderTraversal(from?: number) {
        if (this.rootNode == null){
            return;
        }
        let nodes: Queue<TreeNode<H>>  = new Queue<TreeNode<H>>();
        nodes.add(this.rootNode);
        while(!nodes.isEmpty()) {
            let currentNode: TreeNode<H> = nodes.pop();
            console.log("key is:" + currentNode.getKey());
            if(currentNode.getLeftChild() != null) {
                nodes.add(currentNode.getLeftChild());
            }
            if(currentNode.getRightChild() != null) {
                nodes.add(currentNode.getRightChild());
            }
        }

    }
}

It’s a version of Swift that works on the web. In this version of the code, we will just traverse from the root in the breadth first manner. Hence we will just avoid the parameter from which would tell us from which key. See, I have made that optional so we don’t need to pass it.

Get updates?

Leave this field empty if you're human:

I like writing Typescript 🙂

Test it

First, how do we compile the above code? There are several ways to do that, here’s what I did,

1. Install Typescript via npm install -g typescript 
2. Keep all the above code in a file e.g. TreeBFS.ts
3. For the purpose of testing it create a 4 level tree in the file TreeBFS.ts (code for this below)
4. Compile it using tsc TreeBFS.ts which will generate the TreeeBFS.js
5. Run the javascript file via node TreeBFS.js (assuming you have node installed)

For the purpose of testing it, let’s  create a tree with 4 levels and traverse it.

let tree = new BinaryTree<number>();
tree.addNode(7);
tree.addNode(8);
tree.addNode(4);
tree.addNode(3);
tree.addNode(5);
tree.addNode(2);
tree.addNode(9);
tree.addNode(11);
tree.levelOrderTraversal();

The Javascript code

Here’s all the Javascript code generated after I compiled the Typescript file.

Conclusion

Personally, I would love to brush up on data structures when working with a new language. However time doesn’t always permit it, so I ended up building and releasing Android apps using Ionic/Angular with Typescript before I could do this. However, it’s never too late and as I said, I will update this post or make a new post showing how to do this in iOS/Swift.