Binary Tree traversal program written in JS to demonstrate Breadth-First Search & Depth-First Search techniques.

binaryTreeTraversals.js

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  // Method to insert a node into the Binary Search Tree rooted at this node
  insert(data) {
    if (data <= this.data) {
      this.left === null ? this.left = new Node(data) : this.left.insert(data);
    } else {
      this.right === null ? this.right = new Node(data) : this.right.insert(data);
    }
  }
}


/*
  BREADTH-FIRST SEARCH
     -> Level Order Traversal
*/

function levelOrder(root, queue = [], result = []) {
    if (!root) return

    queue.push(root)
    while(queue.length) {
        const currentNode = queue.shift();
        result.push(currentNode.data)
        if(currentNode.left) queue.push(currentNode.left)
        if(currentNode.right) queue.push(currentNode.right)
    }

    return result;
}


/*
  DEPTH-FIRST SEARCH
     -> Pre-Order Traversal
     -> In-Order Traversal
     -> Post-Order Traversal
*/

function preOrder(root, nodelist = []) {  // D L R
    if (root) {
        nodelist.push(root.data);         // Push Data
        preOrder(root.left, nodelist);    // Visit Left Subtree
        preOrder(root.right, nodelist);   // Visit Right Subtree
    }

    return nodelist;
}

function inOrder(root, nodelist = []) {  // L D R
    if (root) {
        inOrder(root.left, nodelist);    // Visit Left Subtree
        nodelist.push(root.data);        // Push Data
        inOrder(root.right, nodelist);   // Visit Right Subtree
    }

    return nodelist;
}

function postOrder(root, nodelist = []) {  // L R D
    if (root) {
        postOrder(root.left, nodelist);    // Visit Left Subtree
        postOrder(root.right, nodelist);   // Visit Right Subtree
        nodelist.push(root.data);          // Push Data
    }

    return nodelist;
}


/* Creating the root node 
   with example tree for testing

	           M
           	  / \
		 B   Q
       		/ \   \
	       A   C   Z
*/

const root = new Node('M');

// Insert nodes into the BST using the insert method
root.insert('B');
root.insert('Q');
root.insert('Z');
root.insert('A');
root.insert('C');


// BREADTH-FIRST TRAVERSAL
levelOrder(root))  // [ 'M', 'B', 'Q', 'A', 'C', 'Z' ]

// DEPTH-FIRST TRAVERSALS
preOrder(root)    // [ 'M', 'B', 'A', 'C', 'Q', 'Z' ]
inOrder(root)     // [ 'A', 'B', 'C', 'M', 'Q', 'Z' ]
postOrder(root)   // [ 'A', 'C', 'B', 'Z', 'Q', 'M' ]