DFS and BFS Solution

by Clay Anderson

HTML

<div id="output"></div>

JavaScript

/*

Example tree:

         A
      /     \        
     B       C
   /   \    /  \
  D     E  F    G

DFS Output: DEBFGCA
BFS Output: ABCDEFG
BFS Output (alternating direction): ACBDEFG

*/

/*
class Node {
	name;
	left;
  right;
}
*/

const myTree = {
	name: 'A',
  left: {
  	name: 'B',
    left: {
    	name: 'D'
    },
    right: {
    	name: 'E'
    }
  },
  right: {
  	name: 'C',
    left: {
    	name: 'F'
    },
    right: {
    	name: 'G'
    }
  }
};

function DFS(node) {
	if (!node) {
  	return undefined;
  }
  const left = DFS(node.left) || '';
  const right = DFS(node.right) || '';

	return left + right + node.name;
}

function BFS(node) {
	let result = '';
  let row = [node];
	while (row.length > 0) {
  	row.forEach(n => result += n.name);
    
    let newRow = [];
    // flat map nodes children
    row = row.reduce((accumulator, n) => {
			if (n.left) {
				accumulator.push(n.left);
      }
    	if (n.right) {
      	accumulator.push(n.right);
      }
      return accumulator;
    }, []);
  }  
	return result;
}

function GoofyBFS(node) {
  let result = '';
  let row = [node];
  let rtl = false;
	while (row.length > 0) {
  	row.forEach(n => result += n.name);
    
    rtl = !rtl;
    row.reverse();
    // flat map nodes children
    row = row.reduce((accumulator, n) => {
      if (n.left) {
        accumulator.push(n.left);
      }
      if (n.right) {
        accumulator.push(n.right);
      }
      return accumulator;
    }, []);
    if (rtl) {
    	row.reverse();
    }
  }  
	return result;
}


document.getElementById("output").innerHTML += DFS(myTree) === 'DEBFGCA' ? 'PASS' : 'FAIL: ' + DFS(myTree);
document.getElementById("output").innerHTML += "<br>";
document.getElementById("output").innerHTML += BFS(myTree) === 'ABCDEFG' ? 'PASS' : 'FAIL: ' + BFS(myTree);
document.getElementById("output").innerHTML += "<br>";
document.getElementById("output").innerHTML += GoofyBFS(myTree) === 'ACBDEFG' ? 'PASS' : 'FAIL: ' + GoofyBFS(myTree);