Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Binary Search Tree in Typescript

fueanta May 17th, 2020 (edited) 936 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Node<T> {
  2.     public data: T;
  3.     public left: Node<T> | null;
  4.     public right: Node<T> | null;
  5.  
  6.     constructor(data: T) {
  7.         this.data = data;
  8.         this.left = null;
  9.         this.right = null;
  10.     }
  11. }
  12.  
  13. enum TraversalMethod {
  14.     PreOrder,
  15.     InOrder,
  16.     PostOrder
  17. }
  18.  
  19. export default class BST<T> {
  20.     private root: Node<T> | null;
  21.  
  22.     constructor() {
  23.         this.root = null;
  24.     }
  25.  
  26.     public insert = (data: T): void => {
  27.         const newNode: Node<T> = new Node<T>(data);
  28.         this.root = BST.insertionHelper(this.root, newNode);
  29.     }
  30.  
  31.     private static insertionHelper = <T>(root: Node<T> | null, newNode: Node<T>): Node<T> => {
  32.         if (root) {
  33.             if (newNode.data < root.data) root.left = BST.insertionHelper(root.left, newNode);
  34.             else if (newNode.data > root.data) root.right = BST.insertionHelper(root.right, newNode);
  35.             return root;
  36.         }
  37.         return newNode;
  38.     }
  39.  
  40.     public contains = (data: T): boolean => BST.containmentHelper(this.root, data);
  41.  
  42.     private static containmentHelper = <T>(root: Node<T> | null, data: T): boolean => {
  43.         if (root) {
  44.             if (data < root.data) return BST.containmentHelper(root.left, data);
  45.             else if (data > root.data) return BST.containmentHelper(root.right, data);
  46.             else return true;
  47.         }
  48.         return false;
  49.     }
  50.  
  51.     public delete = (data: T): void => {
  52.         this.root = BST.deletionHelper(this.root, data);
  53.     }
  54.  
  55.     private static deletionHelper = <T>(root: Node<T> | null, data: T): Node<T> | null => {
  56.         if (root) {
  57.             if (data < root.data) root.left = BST.deletionHelper(root.left, data);
  58.             else if (data > root.data) root.right = BST.deletionHelper(root.right, data);
  59.             else {
  60.                 if (root.left && root.right) {
  61.                     let minInRight: Node<T> = BST.getNodeWithMinVal(root.right);
  62.                     root.data = minInRight.data;
  63.                     root.right = BST.deletionHelper(root.right, minInRight.data);
  64.                 }
  65.                 else if (root.left) root = root.left;
  66.                 else if (root.right) root = root.right;
  67.                 else root = null;
  68.             }
  69.         }
  70.         return root;
  71.     }
  72.  
  73.     public depthFirstTraverse = (taskFunc: (data: T) => unknown, traversalMethod: TraversalMethod): void => BST.depthFirstTraverseHelper(this.root, taskFunc, traversalMethod);
  74.  
  75.     private static depthFirstTraverseHelper = <T>(root: Node<T> | null, taskFunc: (data: T) => unknown, traversalMethod: TraversalMethod): void => {
  76.         if (root) {
  77.             if (traversalMethod === TraversalMethod.PreOrder) taskFunc(root.data);
  78.             BST.depthFirstTraverseHelper(root.left, taskFunc, traversalMethod);
  79.             if (traversalMethod === TraversalMethod.InOrder) taskFunc(root.data);
  80.             BST.depthFirstTraverseHelper(root.right, taskFunc, traversalMethod);
  81.             if (traversalMethod === TraversalMethod.PostOrder) taskFunc(root.data);
  82.         }
  83.     }
  84.  
  85.     public breadthFirstTraverse = (taskFunc: (data: T) => unknown): void => {
  86.         if (this.root) {
  87.             const queue: Array<Node<T>> = [this.root];
  88.             while (queue.length) {
  89.                 const node: Node<T> = queue.splice(0, 1)[0]; // avoided queue.shift() since it returns Node<T> | undefined
  90.                 taskFunc(node.data);
  91.                 if (node.left) queue.push(node.left);
  92.                 if (node.right) queue.push(node.right);
  93.             }
  94.         }
  95.     }
  96.  
  97.     public getMinValue = (): T | undefined => this.root ? BST.getNodeWithMinVal(this.root).data : undefined;
  98.  
  99.     private static getNodeWithMinVal = <T>(root: Node<T>): Node<T> => root.left ? BST.getNodeWithMinVal(root.left) : root;
  100.  
  101.     public getMaxValue = (): T | undefined => this.root ? BST.getNodeWithMaxVal(this.root).data : undefined;
  102.  
  103.     private static getNodeWithMaxVal = <T>(root: Node<T>): Node<T> => root.right ? BST.getNodeWithMaxVal(root.right) : root;
  104. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top