function height(root) {
  if (root === null) {
    return 0;
  } else {
    const lHeight = height(root.left);
    const rHeight = height(root.right);
    if (lHeight > rHeight) {
      return lHeight + 1;
    } else {
      return rHeight + 1;
    }
  }
}
function getNodesByLevel(root, level) {
  const result = [];
  function helper(root, level) {
    if (root === null) {
      return;
    }
    if (level === 1) {
      result.push(root.val);
    } else if (level > 1) {
      helper(root.left, level - 1);
      helper(root.right, level - 1);
    }
  }
  helper(root, level);
  return result;
}

const { height } = require('./height');
const { getNodesByLevel } = require('./getNodesByLevel');

function levelOrder(root) {
  const result = [];
  for (let i = 1; i <= height(root); i++) {
    result.push(...getNodesByLevel(root, i));
  }
  return result;
}

function iterativeLevelOrder(root) {
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const temp = queue.shift();
    result.push(temp.val);
    if (temp.left) {
      queue.push(temp.left);
    }
    if (temp.right) {
      queue.push(temp.right);
    }
  }
  return result;
}

const { generateTree } = require('../docs/algo/common/generator');
const {
  recursiveLevelOrder,
  iterativeLevelOrder,
} = require('../docs/algo/tree/levelOrder');
describe('levelOrder', () => {
  const root = generateTree();
  const expectResult = [1, 2, 3, 4, 5];
  it('recursive', () => {
    expect(recursiveLevelOrder(root)).toEqual(expectResult);
  });
  it('iterative', () => {
    expect(iterativeLevelOrder(root)).toEqual(expectResult);
  });
});