Wednesday, February 28, 2018

How to traverse a binary tree in JavaScript?

Overview 

Based on Traverse a Tree - Introduction. How to traverse a binary tree recursively

  • Pre-Order, 
  • In-Order, 
  • Post-Order 
  • Breadth-First
using mocha+chai test framework.

Github Repo: TreeTraversalJS

Source Code


let Queue = require('./Queue');

let print = console.log;

function TreeTraversal() {

    this.PathResult = [];

    this.init = function(first) {

        if(first) this.PathResult = [];
    }
    this.end = function(first) {

        if(first) print(`Path:${JSON.stringify(this.PathResult)}`);
    }
    this.processNode = function(node) {

        this.PathResult.push(node.value);
    }
    this.recursively_PreOrderTraversal = function (t, first) {

        this.init(first);
        this.processNode(t);

        if(t.left) this.recursively_PreOrderTraversal(t.left);
        if(t.right) this.recursively_PreOrderTraversal(t.right);

        this.end(first);
    }
    this.recursively_InOrderTraversal = function (t, first) {

        this.init(first);
        if(t.left) this.recursively_InOrderTraversal(t.left);

        this.processNode(t);

        if(t.right) this.recursively_InOrderTraversal(t.right);

        this.end(first);
    }
    this.recursively_PostOrderTraversal = function(t, first) {

        this.init(first);

        if(t.left) this.recursively_PostOrderTraversal(t.left);
        if(t.right) this.recursively_PostOrderTraversal(t.right);

        this.processNode(t);
        this.end(first);
    }
    this.breadthFirst = function(t) {

        this.init(true);
        let q = new Queue();
        q.enqueue(t);

        while(!q.isEmpty()) {

            let node = q.dequeue();

            this.processNode(node);

            if(node.left) q.enqueue(node.left);
            if(node.right) q.enqueue(node.right);
        }
        this.end(true);
    }
}

module.exports = TreeTraversal;


Unit tests


let assert = require('chai').assert;
let expect = require('chai').expect;
let TreeTraversal = require('../src/TreeTraversal');

/*
                             F
                         /      \
                         B       G
                       /  \       \ 
                       A  D        I
                         / \      /
                        C   E    H

*/
let root = {
    value : "F",
    right : {
        value: "G",
        right:{
            value:"I",
            left : {
               value:"H" 
            }
        }
    },
    left:{
        value:"B",
        left : {
            value:"A"
        },
        right :{
            value:"D",
            left :{
                value:"C"
            },
            right : {
              value:"E"
            }
        }
    }
};

let print = console.log;

function arrayEqual(a0, a1) {
    return a0.join() == a1.join();
}

describe('TreeTraversal', () => {

    let subject;

    before(() => {
        subject = new TreeTraversal();
    });

    describe('recursively_PreOrderTraversal', () => {

        let expected = ["F","B","A","D","C","E","G","I","H"];
        it(`should return ${expected}`, () => {

            subject.recursively_PreOrderTraversal(root, true);
            expect(arrayEqual(expected, subject.PathResult)).to.be.true;
        });
    });
    describe('recursively_InOrderTraversal', () => {

        let expected = ["A","B","C","D","E","F","G","H","I"];
        it(`should return ${expected}`, () => {

            subject.recursively_InOrderTraversal(root, true);
            expect(arrayEqual(expected, subject.PathResult)).to.be.true;
        });
    });
    describe('recursively_PostOrderTraversal', () => {

        let expected = ["A","C","E","D","B","H","I","G","F"];
        it(`should return ${expected}`, () => {

            subject.recursively_PostOrderTraversal(root, true);
            expect(arrayEqual(expected, subject.PathResult)).to.be.true;
        });
    });
    describe('breadthFirst', () => {

        let expected = ["F","B","G","A","D","I","C","E","H"];
        it(`should return ${expected}`, () => {

            subject.breadthFirst(root, true);
            expect(arrayEqual(expected, subject.PathResult)).to.be.true;
        });
    });
});


1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete