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

Stack or Queue?

Breadth-First Search in Typescript

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;
    }
}

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;
    }
}

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());
            }
        }

    }
}

Test it

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)

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

var TreeNode = /** @class */ (function () {
    function TreeNode(key) {
        var _this = this;
        this.getKey = function () { return _this.key; }; //default access modifier is public
        //just to practice the fat arrow function
        this.getLeftChild = function () { return _this.leftChild; };
        this.setLeftChild = function (leftNode) { return _this.leftChild = leftNode; };
        this.key = key;
    }
    TreeNode.prototype.getRightChild = function () {
        return this.rightChild;
    };
    TreeNode.prototype.setRightChild = function (rightChild) {
        this.rightChild = rightChild;
    };
    return TreeNode;
}());
/*
A queue that can be of type T
Generics are great in any language
*/
var Queue = /** @class */ (function () {
    function Queue() {
        var _this = this;
        this.items = [];
        /* Add and pop do the same thing
        One has the fat arrow syntax
        */
        this.add = function (item) { return _this.items.push(item); };
        this.size = function () { return _this.items.length; };
    }
    Queue.prototype.pop = function () {
        return this.items.shift();
    };
    Queue.prototype.isEmpty = function () {
        return this.items.length == 0;
    };
    return Queue;
}());
var BinaryTree = /** @class */ (function () {
    function BinaryTree() {
        var _this = this;
        this.setRoot = function (node) { return _this.rootNode = node; };
    }
    BinaryTree.prototype.addNode = function (key) {
        this.rootNode = this.addNodeByRecursion(this.rootNode, key);
    };
    BinaryTree.prototype.addNodeByRecursion = function (currentNode, key) {
        if (currentNode == null) {
            return new TreeNode(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;
    };
    BinaryTree.prototype.levelOrderTraversal = function (from) {
        if (this.rootNode == null) {
            return;
        }
        var nodes = new Queue();
        nodes.add(this.rootNode);
        while (!nodes.isEmpty()) {
            var currentNode = nodes.pop();
            console.log("key is:" + currentNode.getKey());
            if (currentNode.getLeftChild() != null) {
                nodes.add(currentNode.getLeftChild());
            }
            if (currentNode.getRightChild() != null) {
                nodes.add(currentNode.getRightChild());
            }
        }
    };
    return BinaryTree;
}());
var tree = new BinaryTree();
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();

Conclusion

If you find any of my posts useful and want to support me, you can buy me a coffee :)

https://www.buymeacoffee.com/bhumansoni

Or you can  buying or even try one of my apps on the App Store. 

https://mydaytodo.com/apps/

In addition the above, have a look at a few of the other posts,
How to create radio buttons using vanilla Javascript
https://mydaytodo.com/vanilla-javascript-create-radio-buttons/

How to build a Javascript frontend for Java Spring Boot backend 
https://mydaytodo.com/java-spring-boot-vanilla-javascript-solution/

Or have a look at some useful Javascript tutorials below
https://mydaytodo.com/category/javascript/