README.md

What

Implementation of tree data structure in TypeScript

Why

1. How to search a node in Navigation menu tree?
2. how to find all ancestors for a given node?
3. Iterable interface for tree data structure

Usage

this._tree.traverseDFS((node) => {
  console.log(node);
});

this._tree.traverseBFS((node) => {
  console.log(node);
});

const level4 = this._tree.findByPredicateBFS((node) => {
  return node.link === "/level1/level2/level3/level4"
});
console.log(level4);

const level4Parents = this.getAllParents(level4);
console.log(level4Parents);

for (const node of this._tree) {
  if (node.link === "/admin/overview") {
    console.log("found");
    break;
  }
}

find-insert-index.ts

export function findInsertIndex(comparatorFn, arr, el) {
  let i, len;
  for (i = 0, len = arr.length; i < len; i++) {
    if (comparatorFn(arr[i], el) > 0) {
      break;
    }
  }
  return i;
}

merge-sort.ts

export type Comparator<T> = (x: T, y: T) => number;

/**
 * Sorts an array using merge sort
 */
export function mergeSort<T>(array: T[], comparatorFn: Comparator<T> ): T[] {
  if (array.length <= 1) {
    return array;
  }
  // divide step of mergeSort
  const middle = Math.floor(array.length / 2);
  const left: T[] = array.slice(0, middle);
  const right: T[] = array.slice(middle);

  return merge(mergeSort(left, comparatorFn), mergeSort(right, comparatorFn), comparatorFn);
}

/** Merge (conquer) step of mergeSort */
function merge<T>(left: T[], right: T[], comparatorFn: Comparator<T>): T[] {
  const array: T[] = [];
  let lIndex = 0;
  let rIndex = 0;
  while (lIndex + rIndex < left.length + right.length) {
    const lItem = left[lIndex];
    const rItem = right[rIndex];
    if (lItem == null) {
      array.push(rItem); rIndex++;
    }
    else if (rItem == null) {
      array.push(lItem); lIndex++;
    }
    else if (comparatorFn(lItem, rItem) < 0) { // lItem < rItem
      array.push(lItem); lIndex++;
    }
    else {
      array.push(rItem); rIndex++;
    }
  }
  return array;
}

sidenav-data.ts

import { SidenavItem, SidenavItemType } from './sidenav-item.model';

export const defaultMenu: SidenavItem[] = [
  {
    name: 'Dashboard',
    type: SidenavItemType.DropDown,
    icon: 'dashboard',
    chip: { value: 1, color: 'accent' },
    tooltip: 'Dashboard',
    children: [
      {
        name: 'Dashboard',
        link: '/dashboard',
        icon: 'dashboard'
      },
      {
        name: 'Products',
        link: '/dashboard/products',
        icon: 'dashboard'
      },
      {
        name: 'Orders',
        link: '/dashboard/orders',
        icon: 'dashboard'
      }
    ]
  },
   {
     name: 'Custom components',
     type: SidenavItemType.Separator,
   },
  {
    name: 'Material Widget',
    icon: 'widgets',
    children: [
      {
        name: 'Buttons',
        link: 'material-widgets/buttons',
        icon: 'indeterminate_check_box'
      },
      {
        name: 'List',
        link: 'material-widgets/list',
        icon: 'list'
      },
      {
        name: 'Stepper',
        link: 'material-widgets/stepper',
        icon: 'view_week'
      },
      {
        name: 'Expansion',
        link: 'material-widgets/expansion',
        icon: 'web_aaset'
      },
      {
        name: 'Progress Spinner',
        link: 'material-widgets/spinner',
        icon: 'cached'
      },
      {
        name: 'Cards',
        link: 'material-widgets/cards',
        icon: 'crop_16_9'
      },
      {
        name: 'Icons',
        link: 'material-widgets/icons',
        icon: 'gif'
      },
      {
        name: 'AutoComplete',
        link: 'material-widgets/autocomplete',
        icon: 'get_app'
      },
      {
        name: 'CheckBox',
        link: 'material-widgets/checkbox',
        icon: 'check_box'
      },
      {
        name: 'DatePicker',
        link: 'material-widgets/datepicker',
        icon: 'date_range'
      },

      {
        name: 'Slider',
        link: 'material-widgets/slider',
        icon: 'keyboard_tab'
      },
      {
        name: 'Slide Toggle',
        link: 'material-widgets/slide-toggle',
        icon: 'album'
      },
      {
        name: 'Menu',
        link: 'material-widgets/menu',
        icon: 'menu'
      },
      {
        name: 'Progress Bar',
        link: 'material-widgets/progress-bar',
        icon: 'trending_flat'
      },
      {
        name: 'Input',
        link: 'material-widgets/input',
        icon: 'input'
      },
      {
        name: 'Radio',
        icon: 'radio_button_checked',
        link: 'material-widgets/radio'
      },
      {
        name: 'Select',
        icon: 'select_all',
        link: 'material-widgets/select'
      }
    ]
  },
  {
    name: 'Tables',
    icon: 'list',
    chip: { value: 3, color: 'accent' },
    children: [
      {
        name: 'Fixed',
        icon: 'filter_list',
        link: 'tables/fixed'
      },
      {
        name: 'Feature',
        icon: 'done_all',
        link: 'tables/featured'
      },
      {
        name: 'Responsive Tables',
        icon: 'filter_center_focus',
        link: 'tables/responsive'
      }
    ]
  },
  {
    name: 'Guarded Routes',
    icon: 'mode_edit',
    link: '/dashboard/guarded-routes'
  },
  {
    name: 'Scrumboard',
    link: '/home',
    icon: 'grade'
  },
  {
    name: 'Applications',
    icon: 'view_module',
    children: [
      {
        name: 'Products',
        link: '/dashboard/products',
        icon: 'dashboard'
      },
      {
        name: 'mail',
        icon: 'mail',
        link: 'mail/mail'
      },
      {
        name: 'Editor',
        icon: 'editor',
        link: 'editor/editor'
      }
    ]
  },
  {
    name: 'Pages',
    icon: 'content_copy',
    children: [
      {
        name: 'Login',
        icon: 'work',
        link: '../login'
      },
      {
        name: 'Services',
        icon: 'local_laundry_service',
        link: 'pages/services'
      },
      {
        name: 'Contact',
        icon: 'directions',
        link: 'pages/contact'
      }
    ]
  },
  {
    name: 'Experiments',
    icon: 'pie_chart_outlined',
    children: [
      {
        name: 'experiments',
        icon: 'view_list',
        link: '/experiments'
      },
      {
        name: 'experiments1',
        icon: 'show_chart',
        link: '/experiments/experiment1'
      },
      {
        name: 'experiments3',
        icon: 'pie_chart',
        link: '/experiments/experiment2'
      },
      {
        name: 'Radio',
        icon: 'radio_remove_me',
        link: 'radio_remove_me/radio'
      }
    ]
  },
  {
    name: 'Admin',
    icon: 'map',
    children: [
      {
        name: 'overview',
        icon: 'directions',
        link: '/admin'
      },
      {
        name: 'overview1',
        icon: 'directions',
        link: '/admin/overview1'
      },
      {
        name: 'overview2',
        icon: 'directions',
        link: '/admin/overview2'
      },
      {
        name: 'overview3',
        icon: 'directions',
        link: '/admin/overview3'
      }
    ]
  },
  {
    name: 'Multi-Level Menu',
    icon: 'menu',
    children: [
      {
        name: 'Level 1',
        link: '/level1',
        children: [
          {
            name: 'Level 2',
            link: '/level1/level2',
            children: [
              {
                name: 'Level 3',
                link: '/level1/level2/level3',
                children: [
                  {
                    name: 'Level 4',
                    link: '/level1/level2/level3/level4',
                    children: [
                      {
                        name: 'Level 5',
                        link: '/level1/level2/level3/level4/level5'
                      }
                    ]
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
];

sidenav-item.model.ts

import {TreeNode} from "./tree";

export enum SidenavItemType {
  Link = 'link',
  DropDown = 'dropDown',
  Icon = 'icon',
  Separator = 'separator',
  ExtLink = 'extLink'
}

export interface SidenavItem extends TreeNode<SidenavItem> {
  name: string;  
  type?: SidenavItemType; 
  icon?: string; 
  link?: string; 
  chip?: { value: number; color?: string };
  tooltip?: string;  
  disabled?: boolean;  
}

test.ts

import { defaultMenu } from './sidenav-data';
import {Tree} from "./tree";
import { SidenavItem } from './sidenav-item.model';

export class  Test {
  private _tree: Tree<SidenavItem>;

  constructor() {
    this._tree = new Tree<SidenavItem>({name:'root', children: defaultMenu});
    this._tree.traverseDFS((node)=> {
      console.log(node);
    });

    this._tree.traverseBFS((node)=> {
      console.log(node);
    });
    const level4 = this._tree.findByPredicateBFS((node) => {
      return node.link === "/level1/level2/level3/level4"
    });
    console.log(level4);

    const level4Parents = this._tree.getAllParents(level4);
    console.log(level4Parents)
     
    for (const node of this._tree) {
      if (node.link === "/admin/overview") {
        console.log("found");
        break;
      }
    }
  }
}

tree.model.ts

import {Comparator, mergeSort} from "./merge-sort";
import {findInsertIndex} from "./find-insert-index";

export {Comparator} from "./merge-sort";

/**
 * // Usage examples
 * this._tree.traverseDFS((node)=> {
 *    console.log(node);
 * });
 *
 * this._tree.traverseBFS((node)=> {
 *    console.log(node);
 * });
 *
 * const level4 = this._tree.findByPredicateBFS((node) => {
 *    return node.link === "/level1/level2/level3/level4"
 * });
 * console.log(level4);
 *
 * const level4Parents = this.getAllParents(level4);
 * console.log(level4Parents)
 *
 * for(const node of this._tree) {
 *   if(node.link ==="/admin/overview") {
 *     console.log("found");
 *     break;
 *   }
 * }
 */


export enum TraversalStrategy {
  PreOrder,
  PostOrder
}

export interface TreeNode<T> {
  parent?: T;
  children?: T[];
}

export interface TreeConfig<T> {
  nodeComparatorFn?: Comparator<T>;
}

export class Tree<T extends TreeNode<T>> implements Iterable<T> {
  config: TreeConfig<T> = {};

  root: T;

  constructor(root: T, config?: TreeConfig<T>) {
    this.root = this.addParentLinks(root);
  }

  private addParentLinks(parent: T): T {
    if (parent.children) {

      //mergeSort children
      if (this.config && this.config.nodeComparatorFn) {
        parent.children = mergeSort<any>(parent.children, this.config.nodeComparatorFn);
      }

      // add a parent link to a child structure
      parent.children.forEach((d) => {
        // each child gets marked with a parent
        d.parent = parent;
        // then marks its own children with itself
        this.addParentLinks(d);
      });
    } else {
      parent.children = []
    }
    return parent;
  }


  isRoot(node: T) {
    return node.parent === undefined;
  }

  isLeaf(node: T) {
    return node.children.length === 0;
  }

  add(node: T, toNode: T) {
    const parent = toNode ? this.findBFS(toNode) : null;
    if (parent) {
      // TODO: Find the index to insert the child using findInsertIndex()
      parent.children.push(node);
    } else {
      if (!this.root) {
        this.root = node;
      } else {
        return 'Root node is already assigned';
      }
    }
  }

  remove(node: T) {
    if (this.root === node) {
      this.root = null;
    }

    const queue = [this.root];
    while (queue.length) {
      const _node = queue.shift();
      for (let i = 0; i < _node.children.length; i++) {
        if (_node.children[i] === node) {
          _node.children.splice(i, 1);
        } else {
          queue.push(_node.children[i]);
        }
      }
    }
  }

  contains(node: T) {
    return !!this.findBFS(node);
  }

  findBFS(node: T) {
    const queue = [this.root];
    while (queue.length) {
      const _node = queue.shift()!;
      if (_node === node) {
        return _node;
      }
      for (const child of _node.children) {
        queue.push(child);
      }
    }
    return null;
  }

  findByPredicateBFS(predicate: (node: T) => boolean): T {
    const queue = [this.root];
    while (queue.length) {
      const _node = queue.shift()!;
      if (predicate(_node)) {
        return _node;
      }
      for (const child of _node.children) {
        queue.push(child);
      }
    }
    return null;
  }

  findByPredicateDFS(predicate: (node: T) => boolean, strategy: TraversalStrategy = TraversalStrategy.PreOrder): T {
    //TODO
    return null;
  }

  private _preOrder(node: T, fn: (node: T) => any) {
    if (node) {
      if (fn) {
        fn(node);
      }
      for (const child of node.children) {
        this._preOrder(child, fn);
      }
    }
  }

  private _postOrder(node: T, fn: (node: T) => any) {
    if (node) {
      for (const child of node.children) {
        this._postOrder(child, fn);
      }
      if (fn) {
        fn(node);
      }
    }
  }

  traverseDFS(fn: (node: T) => any, method: TraversalStrategy = TraversalStrategy.PreOrder) {
    const current = this.root;
    if (method = TraversalStrategy.PreOrder) {
      this._postOrder(current, fn)
    } else {
      this._preOrder(current, fn);
    }
  }

  traverseBFS(fn: (node: T) => any) {
    const queue = [this.root];
    while (queue.length) {
      const node = queue.shift();
      if (fn) {
        fn(node);
      }
      for (const child of node.children) {
        queue.push(child);
      }
    }
  }

  * [Symbol.iterator](): IterableIterator<T> {
    const queue = [this.root];
    while (queue.length) {
      const node = queue.shift()!;
      yield node;
      for (const child of node.children) {
        queue.push(child);
      }
    }
  }

  getAllParents(item: T): T[] {
    const parents: T[] = [];
    parents.unshift(item);
    let parent = item.parent;
    while (parent) {
      parents.unshift(parent);
      parent = parent.parent;
    }
    return parents;
  }

}

export interface TreeNode<T> {
parent?: T;
children?: T[];
}

This should not be a predefined structure. The algo should infer structure automatically. A good case for a recursive function.