Traversal

Recursive TreeNode Traversal Algorithm

traversal.js

class TreeNode {
  constructor(val, left, right) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

const preOrderTraversal = (node, result = []) => {
  if (!node) return result;
  result.push(node.val);
  preOrderTraversal(node.left, result);
  preOrderTraversal(node.right, result);
  return result;
};

const inOrderTraversal = (node, result = []) => {
  if (!node) return result;
  inOrderTraversal(node.left, result);
  result.push(node.val);
  inOrderTraversal(node.right, result);
  return result;
};

const postOrderTraversal = (node, result = []) => {
  if (!node) return result;
  postOrderTraversal(node.left, result);
  postOrderTraversal(node.right, result);
  result.push(node.val);
  return result;
};

traversal.spec.js

describe("traversal", () => {
  const treeNode = new TreeNode(
    0,
    new TreeNode(1, new TreeNode(3), new TreeNode(5)),
    new TreeNode(2, new TreeNode(4), new TreeNode(6))
  );

  it("should returns preOrder array", () => {
    expect(preOrderTraversal(treeNode)).toEqual([0, 1, 3, 5, 2, 4, 6]);
  });

  it("should returns inOrder array", () => {
    expect(preOrderTraversal(treeNode)).toEqual([3, 1, 5, 0, 4, 2, 6]);
  });

  it("should returns postOrder array", () => {
    expect(postOrderTraversal(treeNode)).toEqual([3, 5, 1, 4, 6, 2, 0]);
  });
});