Binary tree traversal

bin_tree_traversal.js

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


function inOrder(tree) {
  const array = [];
  if (!tree) { return array; }

  if (typeof(tree) === 'object' && 'left' in tree) {
    array.push(inOrder(tree.left));
  }

  if (typeof(tree) !== 'object') {
    array.push(tree);
  } else if (typeof(tree) === 'object' && 'value' in tree) {
    array.push(tree.value);
  }

  if (typeof(tree) === 'object' && 'right' in tree) {
    array.push(inOrder(tree.right));
  }

  return array.flat();
}


inOrder(tree);


function preOrder(tree) {
  const array = [];
  if (!tree) { return array; }

  if (typeof(tree) !== 'object') {
    array.push(tree);
  } else if (typeof(tree) === 'object' && 'value' in tree) {
    array.push(tree.value);
  }

  if (typeof(tree) === 'object' && 'left' in tree) {
    array.push(preOrder(tree.left));
  }

  if (typeof(tree) === 'object' && 'right' in tree) {
    array.push(preOrder(tree.right));
  }

  return array.flat();
}


preOrder(tree);


function postOrder(tree) {
  const array = [];
  if (!tree) { return array; }

  if (typeof(tree) === 'object' && 'left' in tree) {
    array.push(postOrder(tree.left));
  }

  if (typeof(tree) === 'object' && 'right' in tree) {
    array.push(postOrder(tree.right));
  }

  if (typeof(tree) !== 'object') {
    array.push(tree);
  } else if (typeof(tree) === 'object' && 'value' in tree) {
    array.push(tree.value);
  }

  return array.flat();
}


postOrder(tree);


function levelOrder(tree) {
  const array = [];
  if (!tree) { return array; }

  const queue = [];
  queue.push(tree);
  while (queue.length > 0) {
    const item = queue.shift();

    if (typeof(item) !== 'object') {
      array.push(item);
    } else if (typeof(item) === 'object' && 'value' in item) {
      array.push(item.value);
    }
    
    if (typeof(item) === 'object' && 'left' in item) {
      queue.push(item.left);
    }

    if (typeof(item) === 'object' && 'right' in item) {
      queue.push(item.right);
    }
  }
  
  return array;
}


levelOrder(tree);

Given tree has the following structure.

graph G {
  A -- B;
  A -- C;
  B -- D;
  B -- E;
  C -- F;
  C -- G;
}

And, these functions return the following values.

inOrder(tree);
// => ['D', 'B', 'E', 'A', 'F', 'C', 'G']

preOrder(tree);
//  => ['A', 'B', 'D', 'E', 'C', 'F', 'G']

postOrder(tree);
// => ['D', 'E', 'B', 'F', 'G', 'C', 'A']

levelOrder(tree);
// => ['A', 'B', 'C', 'D', 'E', 'F', 'G']