Utils to manage perfect binary trees

binary-tree.ts

import { TreeNode } from './node';

export class PerfectBinaryTree<T> {
  /**
   * The height or levels the binary tree
   */
  private _height: number;
  public get height(): number {
    return this._height;
  }
  public set height(value: number) {
    this._height = value;
    this.children = this.calculateChildren(value);
  }

  /**
   * The tree's root
   */
  rootNode: TreeNode<T>;

  /**
   * The number of nodes in the tree
   */
  children: number;

  /**
   * The leaves of the tree from left to right
   */
  leaves: TreeNode<T>[] = [];

  /**
   * Just init the with null as data
   */
  constructor();
  /**
   * Init the tree with all nodes and null as their data
   * @param height
   */
  // tslint:disable-next-line: unified-signatures
  constructor(height: number);
  /**
   * Given a pre-order array construct all the tree
   * @param preOrderArray
   */
  constructor(preOrderArray: T[]);
  constructor(heightOrArray?: number | T[]) {
    this.rootNode = new TreeNode(null);

    if (typeof heightOrArray === 'number') {
      const height = heightOrArray;
      this.height = height;
      this.initFromHeight(height);
    } else {
      const preOrderArray = heightOrArray;
      this.initFromPreOrderArray(preOrderArray);
    }
  }

  preOrder(callback: (node: TreeNode<T>) => any) {
    const traversePreOrderFn = (currentNode: TreeNode<T>) => {
      if (currentNode !== null) {
        callback(currentNode);
        traversePreOrderFn(currentNode.left);
        traversePreOrderFn(currentNode.right);
      }
    };

    traversePreOrderFn(this.rootNode);
  }

  postOrder(callback: (node: TreeNode<T>) => any) {
    const traversePostOrderFn = (currentNode: TreeNode<T>) => {
      if (currentNode !== null) {
        traversePostOrderFn(currentNode.left);
        traversePostOrderFn(currentNode.right);
        callback(currentNode);
      }
    };

    traversePostOrderFn(this.rootNode);
  }

  inOrder(callback: (node: TreeNode<T>) => any) {
    const traverseInOrderFn = (currentNode: TreeNode<T>) => {
      if (currentNode !== null) {
        traverseInOrderFn(currentNode.left);
        callback(currentNode);
        traverseInOrderFn(currentNode.right);
      }
    };

    traverseInOrderFn(this.rootNode);
  }

  /**
   * Return the pre-order array that represents the tree
   * @returns pre-order array
   */
  getPreOrderArray(): T[] {
    const preOrderArr: T[] = [];

    this.preOrder(node => preOrderArr.push(node.data));

    return preOrderArr;
  }

  /**
   * Init tree given a pre order array
   * @param preOrderArray
   */
  private initFromPreOrderArray(preOrderArray: T[]) {
    const initFromPreOrderArrayFn = (node: TreeNode<T>, subPreOrder: T[]) => {
      node.data = subPreOrder.shift();

      if (subPreOrder.length === 0) {
        this.setLeaf(node);
        return;
      }

      const leftChildren = subPreOrder.slice(0, subPreOrder.length / 2);
      const rightChildren = subPreOrder.slice(
        subPreOrder.length / 2,
        subPreOrder.length
      );

      node.left = new TreeNode(null);
      initFromPreOrderArrayFn(node.left, leftChildren);

      node.right = new TreeNode(null);
      initFromPreOrderArrayFn(node.right, rightChildren);
    };

    initFromPreOrderArrayFn(this.rootNode, preOrderArray);
  }

  /**
   * Init the tree with all nodes and null as their data
   * @param height
   */
  private initFromHeight(height: number) {
    const preOrderArray = new Array(this.children).fill(null);

    this.initFromPreOrderArray(preOrderArray);
  }

  /**
   * Given the height calculate how many children the tree hs
   * @param height
   */
  private calculateChildren(height: number) {
    return Math.pow(2, height) - 1;
  }

  private setLeaf(leaf: TreeNode<T>) {
    this.leaves.push(leaf);
  }
}

node.ts

export class TreeNode<T> {
  private _data: T;
  public get data(): T {
    return this._data;
  }
  public set data(value: T) {
    this._data = value;
  }

  private _left: TreeNode<T>;
  public get left(): TreeNode<T> {
    return this._left;
  }
  public set left(value: TreeNode<T>) {
    this._left = value;
  }

  private _right: TreeNode<T>;
  public get right(): TreeNode<T> {
    return this._right;
  }
  public set right(value: TreeNode<T>) {
    this._right = value;
  }

  private _parent: TreeNode<T>;
  public get parent(): TreeNode<T> {
    return this._parent;
  }
  public set parent(value: TreeNode<T>) {
    this._parent = value;
  }

  constructor(
    data: T,
    left: TreeNode<T> = null,
    right: TreeNode<T> = null,
    parent: TreeNode<T> = null
  ) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.parent = parent;
  }
}