Binary tree as array kata - shows up a lot in coding challenges

binary_tree_to_array.js

let tree = {
   '0': {
       '1': {
          '3': null,
          '4': null },
       '2': {
          '5': null,
          '6': null }
   }
}

function tree_to_array(t,arr=[]) {
   let children = []
   for( k in t ) {
      arr.push( k )
      children.push( t[k] )
   }
   for( let child of children ) {
      if( child === null || child === undefined )
         continue
      tree_to_array( child, arr )
   }
   return arr
}

console.log( tree_to_array( tree ) ) 
// => ["0","1","2","3","4","5","6"]

binary_tree_to_array_non_recursive.js

function breadth_first( node, fn ) {
   let queue = [ node ]
   for( let node of queue ) {
      for( let k in node ) {
          let child = node[k]
          fn( k, child )
          child && queue.push( child )
      }
   }
}

// depth_first is the same as breadth first, but uses a stack instead of a queue
// This produces an array representation of the binary tree
function depth_first( node, fn ) {
   let queue = [ node ]
   while( node = queue.pop() ) {
      for( let k in node ) {
          let child = node[k]
          fn( k, child )
          child && queue.unshift( child )
      }
   }
}


function test() {
    const TREE = {
        0: {
           1: {
             3: null,
             4: null
           },
           2: {
             5: null,
             6: null
          }
       }
    }

    let result = []

    breadth_first( TREE, (k,v) => result.push(k) )

    console.log( result )
}

test()

travers_binary_tree_array.js

function traverse_binary_tree_array( arr, funcs, depth = 0, idx = 0 ) {

    if( idx >= arr.length )
       return 

    let current = arr[idx]

    funcs.preorder && funcs.preorder(  current, depth, idx )

    let leftchild = 1 + idx * 2
    
    traverse_binary_tree_array( arr, funcs, depth+1, leftchild )

    funcs.inorder && funcs.inorder(  current, depth, idx )

    let rightchild = 2 + idx * 2

    traverse_binary_tree_array( arr, funcs, depth+1, rightchild )

    funcs.postorder && funcs.postorder( current, depth, idx )

}

class Visitor {
   constructor() {
      this._preorder = []
      this._inorder = []
      this._postorder = []
   }

   preorder( elt, idx, depth ) {
      this._preorder.push( elt )
   }

   inorder( elt, idx, depth ) {
      this._inorder.push( elt )
   }

   postorder( elt, idx, depth ) {
      this._postorder.push( elt )
   }
}


function traverse_array() {

    const arr = [0,1,2,3,4,5,6]
    const tree = `
        0
    1      2
  3   4  5   6
`
    console.log( 'initial tree', tree )
    console.log( 'array representation', arr )
    let v = new Visitor
    traverse_binary_tree_array( arr, v )
    console.log( 'preorder', v._preorder )
    console.log( 'inorder', v._inorder )
    console.log( 'postorder', v._postorder )
}

traverse_array()

/* output 

initial tree 
        0
    1      2
  3   4  5   6

array representation [ 0, 1, 2, 3, 4, 5, 6 ]
preorder [ 0, 1, 3, 4, 2, 5, 6 ]
inorder [ 3, 1, 4, 0, 5, 2, 6 ]
postorder [  3, 4, 1, 5, 6, 2, 0 ]
*/