{"version":3,"sources":["../src/index.ts","../src/data-structures/linked-list/base-linked-list.ts","../src/data-structures/linked-list/singly-linked-list.ts","../src/data-structures/linked-list/doubly-linked-list.ts","../src/data-structures/queue/queue.ts","../src/data-structures/stack/stack.ts","../src/data-structures/binary-tree/helper/calc.ts","../src/data-structures/binary-tree/helper/compare.ts","../src/enums/binary-tree/index.ts","../src/data-structures/binary-tree/helper/traversal.ts","../src/data-structures/binary-tree/base/binary-tree-base.ts","../src/data-structures/binary-tree/node/node.ts","../src/data-structures/binary-tree/helper/bt-mutation.ts","../src/data-structures/binary-tree/binary-tree.ts","../src/data-structures/binary-tree/helper/bst.ts","../src/data-structures/binary-tree/binary-search-tree.ts"],"sourcesContent":["import SinglyLinkedList from '@/data-structures/linked-list/singly-linked-list';\nimport DoublyLinkedList from '@/data-structures/linked-list/doubly-linked-list';\nimport Queue from '@/data-structures/queue/queue';\nimport Stack from '@/data-structures/stack/stack';\nimport BinaryTree from '@/data-structures/binary-tree/binary-tree';\nimport BinarySearchTree from '@/data-structures/binary-tree/binary-search-tree';\nimport {BTNode} from '@/data-structures/binary-tree/node/node';\nimport {numericCompare} from \"@/data-structures/binary-tree/helper/bst\";\nimport {strCompare} from \"@/data-structures/binary-tree/helper/bst\";\n\nimport {TraversalOrder} from '@/enums/binary-tree/index';\n\nexport {\n  SinglyLinkedList,\n  DoublyLinkedList,\n  Queue,\n  Stack,\n  BinaryTree,\n  BinarySearchTree,\n  TraversalOrder,\n  BTNode,\n  numericCompare,\n  strCompare\n}","/**\n * Represents a node in a linked list.\n * @template V - Type of the value held by the node.\n * @template N - Type of the reference to the next node.\n */\nexport abstract class LLNode<V, N> {\n  abstract val: V;\n  abstract next: N | null;\n}\n\n/**\n * Represents a base linked list.\n * @template V - Type of the value held by the list.\n * @template N - Type of the reference to the nodes in the list.\n */\nexport abstract class BaseLinkedList<V, N> {\n  protected _head: N | null;\n  protected _tail: N | null;\n  protected _length: number;\n\n  protected constructor() {\n    this._head = null;\n    this._tail = null;\n    this._length = 0;\n  }\n\n  /**\n   * Get the reference to the head node of the list.\n   * @returns {N | null} - Reference to the head node.\n   */\n  get head(): N | null {\n    return this._head;\n  }\n\n  /**\n   * Get the reference to the tail node of the list.\n   * @returns {N | null} - Reference to the tail node.\n   */\n  get tail(): N | null {\n    return this._tail;\n  }\n\n  /**\n   * Get the size of the list.\n   * @returns {number} - The size of the list.\n   */\n  get size(): number {\n    return this._length;\n  }\n\n  /**\n   * Check if the list is empty.\n   * @returns {boolean} - Indicates whether the list is empty or not.\n   */\n  get isEmpty(): boolean {\n    return this.size === 0;\n  }\n\n  /**\n   * Add a new node with the provided value to the end of the list.\n   * @param {V} val - Value to be added to the list.\n   * @returns {BaseLinkedList<V, N>} - Updated list.\n   */\n  abstract push(val: V): BaseLinkedList<V, N>;\n\n  /**\n   * Remove and return the value from the end of the list.\n   * @returns {V | undefined} - Removed value.\n   */\n  abstract pop(): V | undefined;\n\n  /**\n   * Remove and return the value from the beginning of the list.\n   * @returns {V | undefined} - Removed value.\n   */\n  abstract shift(): V | undefined;\n\n  /**\n   * Add a new node with the provided value to the beginning of the list.\n   * @param {V} val - Value to be added to the beginning of the list.\n   * @returns {BaseLinkedList<V, N>} - Updated list.\n   */\n  abstract unshift(val: V): BaseLinkedList<V, N>;\n\n  /**\n   * Get the value at the specified index.\n   * @param {number} index - Index of the value to retrieve.\n   * @returns {V | undefined} - Retrieved value.\n   */\n  abstract at(index: number): V | undefined;\n\n  /**\n   * Get the node at the specified index.\n   * @param {number} index - Index of the node to retrieve.\n   * @returns {N | null} - Retrieved node.\n   */\n  abstract nodeAt(index: number): N | null;\n\n  /**\n   * Set the value at the specified index.\n   * @param {number} index - Index where the value needs to be set.\n   * @param {V} val - Value to be set.\n   * @returns {boolean} - Indicates if the value was successfully set or not.\n   */\n  abstract setAt(index: number, val: V): boolean;\n\n  /**\n   * Insert a value at the specified index.\n   * @param {number} index - Index where the value needs to be inserted.\n   * @param {V} val - Value to be inserted.\n   * @returns {boolean} - Indicates if the value was successfully inserted or not.\n   */\n  abstract insertAt(index: number, val: V): boolean;\n\n  /**\n   * Delete the value at the specified index.\n   * @param {number} index - Index where the value needs to be deleted.\n   * @returns {V | undefined} - Deleted value.\n   */\n  abstract deleteAt(index: number): V | undefined;\n\n  /**\n   * Reverse the order of the nodes in the list.\n   * @returns {BaseLinkedList<V, N>} - Reversed list.\n   */\n  abstract reverse(): BaseLinkedList<V, N>;\n\n  /**\n   * Clears the linked list by resetting its properties.\n   * @returns {void}\n   * @timecomplexity O(1) - Constant time as it directly resets the properties.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  clear(): void {\n    this._head = null;\n    this._tail = null;\n    this._length = 0;\n  }\n\n  /**\n   * Checks if the provided index is a valid index within the list.\n   * @param {number} index - Index to be checked.\n   * @returns {boolean} - Indicates if the index is valid.\n   */\n  protected isValidIndex(index: number): boolean {\n    return index >= 0 && index < this._length;\n  }\n}","import { BaseLinkedList, LLNode } from './base-linked-list';\n\n/**\n * Represents a node in a singly linked list.\n * @template T - Type of the value held by the node.\n */\nexport class SLLNode<T> extends LLNode<T, SLLNode<T>>{\n  val: T\n  next: SLLNode<T>\n  constructor(val: T) {\n    super()\n    this.val = val;\n    this.next = null\n  }\n}\n\n/**\n * Represents a singly linked list.\n * @template T - Type of the value held by the list.\n */\nexport default class SinglyLinkedList<T> extends BaseLinkedList<T, SLLNode<T>> {\n  constructor() {\n    super()\n  }\n\n  /**\n   * Create a singly linked list from an array.\n   * @param {T[]} data - Array to create the list from.\n   * @returns {SinglyLinkedList<T>} - Singly linked list created from the array.\n   * @timecomplexity O(n) - Where 'n' is the length of the input array.\n   * @spacecomplexity O(n) - Additional space used is linearly proportional to the length of the input array.\n   */\n  static fromArray<T>(data: T[]): SinglyLinkedList<T> {\n    const list = new SinglyLinkedList<T>();\n\n    for (const item of data) {\n      list.push(item);\n    }\n\n    return list;\n  }\n\n  /**\n   * Adds a new node with the provided value to the end of the list.\n   * @param {T} val - Value to be added to the list.\n   * @returns {SinglyLinkedList<T>} - Updated list.\n   * @timecomplexity O(1) - Constant time complexity as it only adds to the end of the list.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  push(val: T): SinglyLinkedList<T> {\n    const newNode = new SLLNode(val);\n\n    if (this.isEmpty) {\n      this._head = newNode;\n      this._tail = newNode;\n    } else {\n      this._tail!.next = newNode;\n      this._tail = newNode;\n    }\n\n    this._length++;\n\n    return this;\n  }\n\n  /**\n   * Removes and returns the value from the end of the list.\n   * @returns {T | undefined} - Removed value.\n   * @timecomplexity O(n) - Linear time as it may traverse the list to find the last element.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  pop(): T | undefined {\n    if (this._head === null) {\n      return undefined;\n    }\n\n    if (this._head === this._tail) {\n      const val = this._tail.val;\n      this._head = null;\n      this._tail = null;\n      this._length--;\n\n      return val;\n    }\n\n    let currentNode = this._head;\n\n    while (currentNode.next !== this._tail) {\n      currentNode = currentNode.next!;\n    }\n\n    currentNode.next = null;\n    const val = this._tail!.val;\n    this._tail = currentNode;\n    this._length--;\n\n    return val;\n  }\n\n  /**\n   * Removes and returns the value from the beginning of the list.\n   * @returns {T | undefined} - Removed value.\n   * @timecomplexity O(1) - Constant time complexity as it only removes from the beginning of the list.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  shift(): T | undefined {\n    if (this._head === null) {\n      return undefined;\n    }\n\n    const removedNode = this._head;\n\n    if (this._head === this._tail) {\n      this._tail = null;\n    }\n\n    this._head = removedNode.next;\n    this._length--;\n\n    return removedNode.val;\n  }\n\n  /**\n   * Adds a new node with the provided value to the beginning of the list.\n   * @param {T} val - Value to be added to the beginning of the list.\n   * @returns {SinglyLinkedList<T>} - Updated list.\n   * @timecomplexity O(1) - Constant time complexity as it only adds to the beginning of the list.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  unshift(val: T): SinglyLinkedList<T> {\n    const newNode = new SLLNode(val);\n\n    if (this.isEmpty) {\n      this._head = newNode;\n      this._tail = newNode;\n    } else {\n      newNode.next = this._head;\n      this._head = newNode;\n    }\n\n    this._length++;\n\n    return this;\n  }\n\n  /**\n   * Get the value at the specified index.\n   * @param {number} index - Index of the value to retrieve.\n   * @returns {T | undefined} - Retrieved value.\n   * @timecomplexity O(n) - Linear time as it may traverse the list to find the node at the specified index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  at(index: number): T | undefined {\n    const currentNode= this.nodeAt(index);\n\n    if (currentNode !== null) {\n      return currentNode.val;\n    }\n\n    return undefined;\n  }\n\n  /**\n   * Get the node at the specified index.\n   * @param {number} index - Index of the node to retrieve.\n   * @returns {SLLNode<T> | null} - Retrieved node or null if index is invalid.\n   * @timecomplexity O(n) - Linear time as it may traverse the list to find the node at the specified index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  nodeAt(index: number): SLLNode<T> | null {\n    if (!this.isValidIndex(index)) {\n      return null;\n    }\n\n    let currentNode = this._head;\n\n    for (let i: number = 0; i < index; i++) {\n      currentNode = currentNode!.next;\n    }\n\n    return currentNode;\n  }\n\n  /**\n   * Set the value at the specified index.\n   * @param {number} index - Index where the value needs to be set.\n   * @param {T} val - Value to be set.\n   * @returns {boolean} - Indicates if the value was successfully set or not.\n   * @timecomplexity O(n) - Linear time as it may traverse the list to find the node at the specified index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  setAt(index: number, val: T): boolean {\n    const currentNode = this.nodeAt(index);\n\n    if (currentNode !== null) {\n      currentNode.val = val;\n      return true;\n    }\n\n    return false;\n  }\n\n  /**\n   * Insert a value at the specified index.\n   * @param {number} index - Index where the value needs to be inserted.\n   * @param {T} val - Value to be inserted.\n   * @returns {boolean} - Indicates if the value was successfully inserted or not.\n   * @timecomplexity O(n) - Linear time as it may traverse the list to find the node before the specified index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  insertAt(index: number, val: T): boolean {\n    if (index < 0 || index > this._length) {\n      return false;\n    }\n\n    if (index === 0) {\n      return !!this.unshift(val);\n    }\n\n    if (index === this._length) {\n      return !!this.push(val);\n    }\n\n    const newNode = new SLLNode(val);\n\n    const beforeNode = this.nodeAt(index - 1);\n    const afterNode = beforeNode!.next;\n\n    beforeNode!.next = newNode;\n    newNode.next = afterNode;\n\n    this._length++;\n\n    return true;\n  }\n\n  /**\n   * Delete the value at the specified index.\n   * @param {number} index - Index where the value needs to be deleted.\n   * @returns {T | undefined} - Deleted value or undefined if index is invalid.\n   * @timecomplexity O(n) - Linear time as it may traverse the list to find the node before the specified index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  deleteAt(index: number): T | undefined {\n    if (!this.isValidIndex(index)) {\n      return undefined;\n    }\n\n    if (index === 0) {\n      return this.shift();\n    }\n\n    if (index === this._length - 1) {\n      return this.pop();\n    }\n\n    const beforeNode = this.nodeAt(index - 1);\n\n    if (beforeNode !== null) {\n      const removedNode = beforeNode!.next;\n      beforeNode.next = removedNode!.next;\n      this._length--;\n\n      return removedNode!.val;\n    }\n\n    return undefined;\n  }\n  /**\n   * Reverse the order of the nodes in the list.\n   * @returns {SinglyLinkedList<T>} - The reversed list.\n   * @timecomplexity O(n) - Linear time as it traverses through the entire list to reverse it.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  reverse(): SinglyLinkedList<T> {\n    [this._head, this._tail] = [this._tail, this._head];\n\n    let currentNode = this._tail;\n\n    let nextNode: SLLNode<T> | null;\n    let prevNode: SLLNode<T> | null = null;\n\n    for (let i = 0; i < this._length; i++) {\n      nextNode = currentNode!.next;\n      currentNode!.next = prevNode;\n      prevNode = currentNode;\n      currentNode = nextNode;\n    }\n\n    return this;\n  }\n\n  /**\n   * Rotate the list by the specified number of positions.\n   * @param {number} n - Number of positions to rotate the list.\n   * @returns {SinglyLinkedList<T>} - The rotated list.\n   * @timecomplexity O(n) - Linear time as it may traverse through the list to perform rotations.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  rotateByN(n: number): SinglyLinkedList<T> {\n    if (n % this._length === 0) return this;\n\n    const rotation = n > 0 ? n % this._length : this._length + (n % this._length);\n\n    let currentNode = this._head;\n    let prevNode = this._head;\n\n    this._tail!.next = this._head;\n\n    for (let i = 0; i < rotation; i++) {\n      prevNode = currentNode;\n      currentNode = currentNode!.next;\n    }\n\n    this._head = currentNode;\n    this._tail = prevNode;\n\n    this._tail!.next = null;\n\n    return this;\n  }\n\n  /**\n   * Convert the list to an array.\n   * @returns {T[]} - An array containing the elements of the list in order.\n   * @timecomplexity O(n) - Linear time as it traverses through the entire list to build the array.\n   * @spacecomplexity O(n) - Additional space used is linearly proportional to the list's length.\n   */\n  toArray(): T[] {\n    const arr: T[] = [];\n    let currentNode = this._head;\n\n    while (currentNode) {\n      arr.push(currentNode.val);\n      currentNode = currentNode.next;\n    }\n\n    return arr;\n  }\n}\n","import { BaseLinkedList, LLNode } from './base-linked-list';\n\n/**\n * Represents a node in a doubly linked list.\n * @template T - Type of the value held by the node.\n */\nclass DLLNode<T> extends LLNode<T, DLLNode<T>> {\n  val: T\n  prev: DLLNode<T> | null;\n  next: DLLNode<T> | null;\n  constructor(val: T) {\n    super()\n    this.val = val\n    this.prev = null;\n    this.next = null;\n  }\n}\n\n/**\n * Represents a doubly linked list.\n * @template T - Type of the value held by the list.\n */\nexport default class DoublyLinkedList<T> extends BaseLinkedList<T, DLLNode<T>>{\n  constructor() {\n    super();\n  }\n\n  /**\n   * Creates a doubly linked list from an array.\n   * @param {T[]} data - Array to create the list from.\n   * @returns {DoublyLinkedList<T>} - Doubly linked list created from the array.\n   * @timecomplexity O(n) - Linear time as it iterates through each element in the input array to create the list.\n   * @spacecomplexity O(n) - Additional space used is directly proportional to the number of elements in the input array and the resulting list.\n   */\n  static fromArray<T>(data: T[]): DoublyLinkedList<T> {\n    const list= new DoublyLinkedList<T>();\n\n    for (const item of data) {\n      list.push(item);\n    }\n\n    return list;\n  }\n\n  /**\n   * Adds a new node with the provided value to the end of the list.\n   * @param {T} val - Value to be added to the list.\n   * @returns {DoublyLinkedList<T>} - Updated list.\n   * @timecomplexity O(1) - Constant time as it adds an element at the end of the list.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  push(val: T): DoublyLinkedList<T> {\n    const newNode = new DLLNode<T>(val);\n\n    if (this.isEmpty) {\n      this._head = newNode;\n      this._tail = newNode;\n    } else {\n      this._tail.next = newNode;\n      newNode.prev = this._tail;\n      this._tail = newNode;\n    }\n\n    this._length++;\n    return this;\n  }\n\n  /**\n   * Removes and returns the value from the end of the list.\n   * @returns {T | undefined} - Removed value or undefined if the list is empty.\n   * @timecomplexity O(1) - Constant time as it removes an element from the end of the list.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  pop(): T | undefined {\n    if (this.isEmpty) {\n      return undefined;\n    }\n\n    const removedNode= this._tail;\n\n    if (this._head === this._tail) {\n      this._tail = null;\n      this._head = null;\n    } else {\n      this._tail = removedNode.prev;\n      this._tail!.next = null;\n    }\n\n    this._length--;\n    return removedNode.val;\n  }\n\n  /**\n   * Removes and returns the value from the beginning of the list.\n   * @returns {T | undefined} - Removed value or undefined if the list is empty.\n   * @timecomplexity O(1) - Constant time as it removes an element from the beginning of the list.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  shift(): T | undefined {\n    if (this.isEmpty) {\n      return undefined;\n    }\n\n    const removedNode = this._head;\n\n    if (this._head === this._tail) {\n      this._tail = null;\n      this._head = null;\n    } else {\n      this._head = removedNode.next;\n      this._head!.prev = null;\n    }\n\n    this._length--;\n    return removedNode.val;\n  }\n\n  /**\n   * Adds a new node with the provided value to the beginning of the list.\n   * @param {T} val - Value to be added to the beginning of the list.\n   * @returns {DoublyLinkedList<T>} - Updated list.\n   * @timecomplexity O(1) - Constant time as it adds an element at the beginning of the list.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  unshift(val: T): DoublyLinkedList<T> {\n    const newNode = new DLLNode<T>(val);\n\n    if (this.isEmpty) {\n      this._head = newNode;\n      this._tail = newNode;\n    } else {\n      newNode.next = this._head;\n      this._head!.prev = newNode;\n      this._head = newNode;\n    }\n\n    this._length++;\n    return this;\n  }\n\n  /**\n   * Returns the value at the specified index in the list.\n   * @param {number} index - Index to retrieve the value from.\n   * @returns {T | undefined} - Value at the index or undefined if the index is out of range.\n   * @timecomplexity O(n) - Linear time in the worst case, as it traverses the list to reach the desired index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  at(index: number): T | undefined {\n    const currentNode = this.nodeAt(index);\n\n    if (currentNode !== null) {\n      return currentNode.val;\n    }\n\n    return undefined;\n  }\n\n  /**\n   * Retrieves the node at the specified index in the list.\n   * @param {number} index - Index to retrieve the node from.\n   * @returns {DLLNode<T> | null} - Node at the index or null if the index is out of range.\n   * @timecomplexity O(n) - Linear time in the worst case, as it traverses the list to reach the desired index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  nodeAt(index: number): DLLNode<T> | null {\n    if (index < 0 || index >= this._length) {\n      return null;\n    }\n\n    let currentNode: DLLNode<T> | null;\n    let count: number;\n\n    // Start from the closer end (head or tail) depending on the index\n    if (index <= this._length / 2) {\n      currentNode = this._head;\n      count = index;\n    } else {\n      currentNode = this._tail;\n      count = this._length - index - 1;\n    }\n\n    const direction = index <= this._length / 2 ? 'next' : 'prev';\n\n    for (let i = 0; i < count; i++) {\n      currentNode = currentNode![direction];\n    }\n\n    return currentNode;\n  }\n\n  /**\n   * Sets the value at the specified index in the list.\n   * @param {number} index - Index where the value should be set.\n   * @param {T} val - Value to set at the index.\n   * @returns {boolean} - True if the value is successfully set, false if the index is out of range.\n   * @timecomplexity O(n) - Linear time in the worst case, as it traverses the list to reach the desired index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  setAt(index: number, val: T): boolean {\n    const currentNode = this.nodeAt(index)\n\n    if (currentNode !== null) {\n      currentNode.val = val;\n      return true;\n    }\n\n    return false;\n  }\n\n  /**\n   * Inserts a new node with the provided value at the specified index in the list.\n   * @param {number} index - Index where the value should be inserted.\n   * @param {T} val - Value to insert at the index.\n   * @returns {boolean} - True if the value is successfully inserted, false if the index is out of range.\n   * @timecomplexity O(n) - Linear time in the worst case, as it might traverse the list to reach the desired index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  insertAt(index: number, val: T): boolean {\n    if (index < 0 || index > this._length) {\n      return false;\n    }\n\n    if (index === 0) {\n      return !!this.unshift(val);\n    }\n\n    if (index === this._length) {\n      return !!this.push(val);\n    }\n\n    const newNode = new DLLNode(val);\n    const beforeNode = this.nodeAt(index - 1);\n    const afterNode = beforeNode!.next;\n\n    beforeNode!.next = newNode;\n    afterNode!.prev = newNode;\n\n    newNode.prev = beforeNode;\n    newNode.next = afterNode;\n\n    this._length++;\n    return true;\n  }\n\n  /**\n   * Deletes the node at the specified index in the list.\n   * @param {number} index - Index of the node to be deleted.\n   * @returns {T | undefined} - Value of the deleted node or undefined if the index is out of range.\n   * @timecomplexity O(n) - Linear time in the worst case, as it might traverse the list to reach the desired index.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  deleteAt(index: number): T | undefined {\n    if (index < 0 || index >= this._length ) {\n      return undefined;\n    }\n\n    if (index === 0) {\n      return this.shift();\n    }\n\n    if (index === this._length - 1) {\n      return this.pop();\n    }\n\n    const removedNode = this.nodeAt(index);\n\n    if (removedNode !== null) {\n      const beforeNode = removedNode!.prev;\n      const afterNode = removedNode!.next;\n\n      beforeNode!.next = afterNode;\n      afterNode!.prev = beforeNode;\n\n      this._length--;\n      return removedNode.val;\n    }\n\n    return undefined;\n  }\n\n  /**\n   * Reverses the order of nodes in the list.\n   * @returns {DoublyLinkedList<T>} - The reversed list.\n   * @timecomplexity O(n) - Linear time, as it traverses the list to reverse the order of nodes.\n   * @spacecomplexity O(1) - Constant space is used regardless of the list size.\n   */\n  reverse(): DoublyLinkedList<T> {\n    let currentNode = this._head;\n    [this._head, this._tail] = [this._tail, this._head];\n\n    while (currentNode) {\n      const next = currentNode.next;\n      [currentNode.prev, currentNode.next] = [currentNode.next, currentNode.prev];\n      currentNode = next;\n    }\n\n    return this;\n  }\n\n  /**\n   * Converts the list into an array of its values.\n   * @returns {T[]} - Array containing the values of the list.\n   * @timecomplexity O(n) - Linear time, as it traverses the list to create the array of values.\n   * @spacecomplexity O(n) - Additional space is directly proportional to the number of elements in the list.\n   */\n  toArray(): T[] {\n    const arr: T[] = [];\n    let currentNode = this._head;\n\n    while (currentNode) {\n      arr.push(currentNode.val);\n      currentNode = currentNode.next;\n    }\n\n    return arr;\n  }\n}\n","import SinglyLinkedList from '../linked-list/singly-linked-list';\n\n/**\n * Queue class represents a basic queue data structure that follows the First-In-First-Out (FIFO) principle.\n * It uses a singly linked list internally for efficient enqueue and dequeue operations.\n * @template T - The type of elements stored in the queue.\n */\nexport default class Queue<T> {\n  list: SinglyLinkedList<T>;\n\n  /**\n   * Creates an instance of the Queue class.\n   * The underlying data structure is a singly linked list.\n   */\n  constructor() {\n    this.list = new SinglyLinkedList();\n  }\n\n  /**\n   * Retrieves the value at the front of the queue.\n   * @returns {T | undefined} The value at the front of the queue, or undefined if the queue is empty.\n   * @timecomplexity O(1) - Constant time complexity as accessing the head of a linked list is a constant time operation.\n   * @spacecomplexity O(1) - Constant space complexity as no additional data structures are used.\n   */\n  get front(): T | undefined {\n    return this.list.head?.val;\n  }\n\n  /**\n   * Retrieves the value at the rear of the queue.\n   * @returns {T | undefined} The value at the rear of the queue, or undefined if the queue is empty.\n   * @timecomplexity O(1) - Constant time complexity as accessing the tail of a linked list is a constant time operation.\n   * @spacecomplexity O(1) - Constant space complexity as no additional data structures are used.\n   */\n  get rear(): T | undefined {\n    return this.list.tail?.val;\n  }\n\n  /**\n   * Returns the number of elements in the queue.\n   * @returns {number} - The size of the queue.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  get size(): number {\n    return this.list.size;\n  }\n\n  /**\n   * Checks if the queue is empty.\n   * @returns {boolean} - True if the queue is empty, false otherwise.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  get isEmpty(): boolean {\n    return this.list.isEmpty;\n  }\n\n  /**\n   * Adds an element to the rear of the queue and returns the new size of the queue.\n   * @param {T} val - The value to enqueue.\n   * @returns {number} - The updated size of the queue.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  enqueue(val: T): number {\n    this.list.push(val);\n    return this.size;\n  }\n\n  /**\n   * Removes and returns the element from the front of the queue.\n   * @returns {T | undefined} - The value dequeued from the front of the queue.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  dequeue(): T | undefined {\n    return this.list.shift();\n  }\n\n  /**\n   * Retrieves the value at the front of the queue without removing it.\n   * @returns {T | undefined} - The value at the front of the queue.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  peek(): T | undefined {\n    return this.list.head?.val;\n  }\n\n  /**\n   * Retrieves the value at the rear of the queue without removing it.\n   * @returns {T | undefined} - The value at the rear of the queue.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  peekRear(): T | undefined {\n    return this.list.tail?.val;\n  }\n\n  /**\n   * Removes all elements from the queue\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  clear(): void {\n    this.list.clear();\n  }\n\n  /**\n   * Returns an array representation of the queue.\n   * @returns {T[]} - An array containing all elements in the queue.\n   * @timecomplexity O(n)\n   * @spacecomplexity O(n)\n   */\n  toArray(): T[] {\n    return this.list.toArray();\n  }\n}\n","import SinglyLinkedList from '../linked-list/singly-linked-list';\n\n/**\n * Represents a stack data structure that follows the Last-In-First-Out (LIFO) principle.\n * It uses a singly linked list internally for efficient push and pop operations.\n * @template T - The type of elements in the stack.\n */\nexport default class Stack<T> {\n  private list: SinglyLinkedList<T>;\n\n  /**\n   * Creates a new instance of the Stack class.\n   * The underlying data structure is a singly linked list.\n   */\n  constructor() {\n    this.list = new SinglyLinkedList();\n  }\n\n  /**\n   * Retrieves the value at the top of the stack.\n   * @returns {T | undefined} The value at the front of the queue, or undefined if the queue is empty.\n   * @timecomplexity O(1) - Constant time complexity as accessing the head of a linked list is a constant time operation.\n   * @spacecomplexity O(1) - Constant space complexity as no additional data structures are used.\n   */\n  get top (): T | undefined {\n    return this.list.head?.val;\n  }\n\n  /**\n   * Returns the number of elements in the stack.\n   * @returns {number} - The size of the stack.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  get size(): number {\n    return this.list.size;\n  }\n\n  /**\n   * Checks if the stack is empty.\n   * @returns {boolean} - True if the stack is empty, false otherwise.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  get isEmpty(): boolean {\n    return this.size === 0;\n  }\n\n  /**\n   * Adds a new element to the top of the stack.\n   * @param {T} val - The value to be pushed onto the stack.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  push(val: T): void {\n    this.list.unshift(val);\n  }\n\n  /**\n   * Removes and returns the element from the top of the stack.\n   * @returns {T | undefined} The value popped from the stack, or undefined if the stack is empty.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  pop(): T | undefined {\n    return this.list.shift();\n  }\n\n  /**\n   * Retrieves the value at the top of the stack without removing it.\n   * @returns {T | undefined} The value at the top of the stack, or undefined if the stack is empty.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  peek(): T | undefined {\n    return this.list.head?.val;\n  }\n  /**\n   * Removes all elements from the stack.\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  clear(): void {\n    this.list.clear();\n  }\n\n  /**\n   * Returns an array representation of the stack.\n   * @returns {T[]} An array containing the elements of the stack in top-to-bottom order.\n   * @timecomplexity O(n)\n   * @spacecomplexity O(n)\n   */\n  toArray(): T[] {\n    return this.list.toArray().reverse();\n  }\n}","import {Key} from \"@/types/binary-tree\";\nimport { BTNode } from '../node/node';\n\n/**\n * Helper class for performing calculations related to binary trees.\n */\nexport class CalcHelper {\n  /**\n   * Calculates the maximum number of nodes at a given depth in a binary tree.\n   * @param {number} depth - The depth of the binary tree.\n   * @returns {number} - The maximum number of nodes at the specified depth.\n   *\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   * @description This function calculates the maximum number of nodes at a given depth in a binary tree\n   * using the formula 2^depth - 1.\n   */\n  static maxNodesAtDepth(depth: number): number {\n    if (depth <= 0 || !Number.isInteger(depth)) {\n      throw new Error('Number of levels must be Integer and greater than 0');\n    }\n    return Math.pow(2, depth) - 1;\n  }\n  \n  /**\n   * Calculates the minimum depth of a binary tree required to achieve a certain number of nodes.\n   * @param {number} size - The number of nodes in the binary tree.\n   * @returns {number} - The minimum depth required to have the specified number of nodes.\n   *\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   * @description This function calculates the minimum depth of a binary tree required to achieve\n   * a certain number of nodes using the formula floor(log2(size + 1)).\n   */\n  static minDepthAtNodesSize(size: number): number {\n    if (size <= 0 || !Number.isInteger(size)) {\n      throw new Error('Number of nodes must be Integer and greater than 0');\n    }\n    return Math.floor(Math.log2(size + 1));\n  }\n  \n  /**\n   * Calculates the minimum depth of a binary tree required to have a certain number of leaves.\n   * @param {number} leaves - The number of leaves in the binary tree.\n   * @returns {number} - The minimum depth required to have the specified number of leaves.\n   *\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   * @description This function calculates the minimum depth of a binary tree required to have\n   * a certain number of leaves using the formula floor(log2(leaves)) + 1.\n   */\n  static minDepthAtLeavesSize(leaves: number): number {\n    if (leaves <= 0 || !Number.isInteger(leaves)) {\n      throw new Error('Number of leaves must be Integer and greater than 0');\n    }\n    return Math.floor(Math.log2(leaves)) + 1;\n  }\n  \n  /**\n   * Calculates the maximum depth of a binary tree.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {number} - The maximum depth of the binary tree.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   * @description This function calculates the maximum depth of a binary tree recursively by\n   * considering the maximum depth of the left and right subtrees.\n   */\n  static maxDepth<K extends Key, V>(root: BTNode<K, V> | null): number {\n    if (root === null) {\n      return 0;\n    }\n    const leftDepth = CalcHelper.maxDepth(root.left);\n    const rightDepth = CalcHelper.maxDepth(root.right);\n    return Math.max(leftDepth, rightDepth) + 1;\n  }\n  \n  /**\n   * Calculates the total number of nodes in a binary tree.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {number} - The total number of nodes in the binary tree.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   * @description This function calculates the total number of nodes in a binary tree\n   * by summing the nodes in the left and right subtrees, including the root.\n   */\n  static calcSize<K extends Key, V>(root: BTNode<K, V> | null): number {\n    if (root === null) {\n      return 0;\n    }\n    return 1 + CalcHelper.calcSize<K, V>(root.left) + CalcHelper.calcSize(root.right);\n  }\n}","import Queue from \"@/data-structures/queue/queue\";\nimport {Key} from \"@/types/binary-tree\";\nimport {BTNode} from \"../node/node\";\nimport {CalcHelper} from \"./calc\";\n\n/**\n * Helper class for comparing binary trees.\n */\nexport class CompareHelper {\n  /**\n   * Checks if two binary trees are equal.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root of the first binary tree.\n   * @param {BTNode<K, V> | null} targetRoot - The root of the second binary tree.\n   * @returns {boolean} True if the trees are equal, false otherwise.\n   *\n   * @timecomplexity O(min(n, m)), where n and m are the number of nodes in the two binary trees.\n   * @spacecomplexity O(min(h1, h2)), where h1 and h2 are the heights of the two binary trees.\n   */\n  static isEqual<K extends Key, V>(root: BTNode<K, V> | null, targetRoot: BTNode<K, V> | null): boolean {\n    if (root === null && targetRoot === null) {\n      return true;\n    }\n    if (root === null || targetRoot === null) {\n      return false;\n    }\n    if (root.val !== targetRoot.val) {\n      return false;\n    }\n    return CompareHelper.isEqual<K, V>(root.left, targetRoot.left) &&\n      CompareHelper.isEqual<K, V>(root.right, targetRoot.right)\n  }\n  \n  /**\n   * Checks if a binary tree is perfect.\n   * A binary tree is considered perfect if all nodes have exactly two children, and all leaf nodes are at the same level.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V>} root - The root of the binary tree.\n   * @returns {boolean} True if the tree is perfect, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   * @description\n   * This method determines if a binary tree is perfect by checking whether all leaf nodes are at the same level\n   * and each non-leaf node has exactly two children. It calculates the depth of the tree and then recursively\n   * verifies the perfect binary tree conditions.\n   */\n  static isPerfect<K extends Key, V>(root: BTNode<K, V>): boolean {\n    const depth = CalcHelper.maxDepth<K, V>(root);\n    return CompareHelper.isPerfectRecursive(root, depth, 0);\n  }\n  \n  /**\n   * Checks if the given binary tree is full.\n   * A binary tree is considered full if each node has either 0 or 2 children.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {boolean} - True if the binary tree is full, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  static isFull<K extends Key, V>(root: BTNode<K, V> | null): boolean {\n    if (!root) {\n      return true;\n    }\n    // Check if the node has either 0 or 2 children\n    if ((root.left === null && root.right !== null) || (root.left !== null && root.right === null)) {\n      return false;\n    }\n    return CompareHelper.isFull(root.left) && CompareHelper.isFull(root.right);\n  }\n  \n  /**\n   * Checks if the given binary tree is complete.\n   * A binary tree is considered complete if all levels, except possibly the last,\n   * are completely filled, and all nodes are as left as possible.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {boolean} - True if the binary tree is complete, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the width of the binary tree (the maximum number of nodes at any level).\n   */\n  static isComplete<K extends Key, V>(root: BTNode<K, V> | null): boolean {\n    if (!root) {\n      return true;\n    }\n    const queue = new Queue<BTNode<K, V>>();\n    queue.enqueue(root)\n    let encounteredNull = false;\n    while (queue.size > 0) {\n      const currentNode = queue.dequeue();\n      if (!currentNode) {\n        encounteredNull = true;\n      } else {\n        if (encounteredNull) {\n          // If a null node is encountered after non-null nodes, the tree is not complete\n          return false;\n        }\n        queue.enqueue(currentNode.left);\n        queue.enqueue(currentNode.right);\n      }\n    }\n    return true;\n  }\n  \n  /**\n   * Checks if the given binary tree is balanced.\n   * A binary tree is considered balanced if the height of the two subtrees of any node\n   * never differs by more than one.\n   *\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {boolean} - True if the binary tree is balanced, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  static isBalanced<K extends Key, V>(root: BTNode<K, V> | null): boolean {\n    if (!root) {\n      return true;\n    }\n    const leftHeight = CalcHelper.maxDepth<K, V>(root.left);\n    const rightHeight = CalcHelper.maxDepth<K, V>(root.right);\n    // Check if the height difference is within the allowed range\n    if (Math.abs(leftHeight - rightHeight) <= 1) {\n      return CompareHelper.isBalanced(root.left) && CompareHelper.isBalanced(root.right);\n    }\n    // If the height difference is greater than 1, the tree is not balanced\n    return false;\n  }\n  \n  /**\n   * Recursive helper function for checking if a binary tree is perfect.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @param {number} depth - The depth of the binary tree.\n   * @param {number} currentLevel - The current level of the tree.\n   * @returns {boolean} True if the tree is perfect, false otherwise.\n   */\n  private static isPerfectRecursive<K extends Key, V>(root: BTNode<K, V> | null, depth: number, currentLevel: number): boolean {\n    if (root === null) {\n      return true;\n    }\n    if (root.left === null && root.right === null) {\n      return depth === currentLevel + 1;\n    }\n    if (root.left === null || root.right === null) {\n      return false;\n    }\n    return (\n      CompareHelper.isPerfectRecursive(root.left, depth, currentLevel + 1) &&\n      CompareHelper.isPerfectRecursive(root.right, depth, currentLevel + 1)\n    );\n  }\n}","export enum TraversalOrder {\n  PreOrder,\n  InOrder,\n  PostOrder,\n  LevelOrder,\n}","import { BTNode } from '../node/node';\nimport {Key, MatchFn, TraversalFn} from '@/types/binary-tree';\nimport Queue from '../../queue/queue';\nimport { TraversalOrder } from \"@/enums/binary-tree\";\n\n/**\n * Helper class for binary tree traversal operations.\n */\nexport class TraversalHelper {\n  /**\n   * Map of traversal orders to their respective iterator functions.\n   */\n  private static iteratorMap = {\n    [TraversalOrder.PreOrder]: TraversalHelper.preOrderIterator,\n    [TraversalOrder.InOrder]: TraversalHelper.inOrderIterator,\n    [TraversalOrder.PostOrder]: TraversalHelper.postOrderIterator,\n    [TraversalOrder.LevelOrder]: TraversalHelper.levelOrderIterator\n  }\n  \n  /**\n   * Gets an iterator for traversing the binary tree based on the specified order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @param {TraversalOrder} [order=TraversalOrder.InOrder] - The order in which nodes should be traversed\n   * (default: InOrder).\n   * @returns {Generator<BTNode<K, V>, void, void>} The iterator for the specified traversal order.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   * @description\n   * This method returns a generator function that iterates through the binary tree nodes based on the specified order.\n   */\n  static getIterator<K extends Key, V>(\n    root: BTNode<K, V> | null,\n    order: TraversalOrder = TraversalOrder.InOrder\n  ): Generator<BTNode<K, V>, void, void> {\n    return TraversalHelper.iteratorMap[order](root)\n  }\n  \n  /**\n   * Executes a provided function once for each node in the binary tree, in a specified order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @param {TraversalFn<K, V>} traversalFn - The function to be executed for each node.\n   * @param {TraversalOrder} [order=TraversalOrder.InOrder] - The order in which nodes should be traversed\n   * (default: InOrder).\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   * @description\n   * This method uses a generator function to iterate through the binary tree nodes based on the specified order.\n   * It then applies the provided function to each node's value, key, and the entire node object.\n   */\n  static forEach<K extends Key, V>(root: BTNode<K, V> | null, traversalFn: TraversalFn<K, V>, order?: TraversalOrder): void {\n    // @ts-ignore\n    for (const n of TraversalHelper.getIterator(root, order)) {\n      traversalFn(n.val, n.key, n);\n    }\n  }\n  \n  /**\n   * Finds the first node in the binary tree that matches a specified condition, in a specified order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @param {MatchFn<K, V>} matchFn - The condition for matching a node.\n   * @param {TraversalOrder} [order=TraversalOrder.InOrder] - The order in which nodes should be traversed\n   * (default: InOrder).\n   * @returns {BTNode<K, V> | null} The first matching node, or null if no match is found.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  static findNode<K extends Key, V>(root: BTNode<K, V> | null, matchFn: MatchFn<K, V>, order?: TraversalOrder): BTNode<K, V> | null {\n    // @ts-ignore\n    for (const n of TraversalHelper.getIterator(root, order)) {\n      if (matchFn(n.val, n.key, n)) {\n        return n;\n      }\n    }\n    return null;\n  }\n  \n  /**\n   * Finds the value of the first node in the binary tree that matches a specified condition, in a specified order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @param {MatchFn<K, V>} matchFn - The condition for matching a node.\n   * @param {TraversalOrder} [order=TraversalOrder.InOrder] - The order in which nodes should be traversed\n   * (default: InOrder).\n   * @returns {V | undefined} The value of the first matching node, or undefined if no match is found.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  static findValue<K extends Key, V>(root: BTNode<K, V> | null, matchFn: MatchFn<K, V>, order?: TraversalOrder ): V | undefined {\n    // @ts-ignore\n    for (const n of TraversalHelper.getIterator(root, order)) {\n      if (matchFn(n.val, n.key, n)) {\n        return n.val;\n      }\n    }\n    return undefined;\n  }\n  \n  /**\n   * Checks if at least one node in the binary tree satisfies a specified condition, in a specified order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @param {MatchFn<K, V>} matchFn - The condition for matching a node.\n   * @param {TraversalOrder} [order=TraversalOrder.InOrder] - The order in which nodes should be traversed\n   * (default: InOrder).\n   * @returns {boolean} True if at least one node matches the condition, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  static some<K extends Key, V>(root: BTNode<K, V> | null, matchFn: MatchFn<K, V>, order?: TraversalOrder): boolean {\n    // @ts-ignore\n    for (const n of TraversalHelper.getIterator(root, order)) {\n      if (matchFn(n.val, n.key, n)) {\n        return true;\n      }\n    }\n    return false;\n  }\n  \n  /**\n   * Checks if every node in the binary tree satisfies a specified condition, in a specified order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @param {MatchFn<K, V>} matchFn - The condition for matching a node.\n   * @param {TraversalOrder} [order=TraversalOrder.InOrder] - The order in which nodes should be traversed\n   * (default: InOrder).\n   * @returns {boolean} True if every node matches the condition, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  static every<K extends Key, V>(root: BTNode<K, V> | null, matchFn: MatchFn<K, V>, order?: TraversalOrder): boolean {\n    // @ts-ignore\n    for (const n of TraversalHelper.getIterator(root, order)) {\n      if (!matchFn(n.val, n.key, n)) {\n        return false;\n      }\n    }\n    return true;\n  }\n  \n  /**\n   * Generates an iterator for traversing the binary tree in level order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {Generator<BTNode<K, V>, void, void>} The iterator for level order traversal.\n   *\n   * @timecomplexity O(N), where N is the number of nodes in the binary tree.\n   * @spacecomplexity O(W), where W is the maximum width of the binary tree.\n   */\n  private static *levelOrderIterator<K extends Key, V>(root: BTNode<K, V> | null): Generator<BTNode<K, V>, void, void> {\n    const queue: Queue<BTNode<K, V>> = new Queue();\n    if (root !== null) {\n      queue.enqueue(root);\n    }\n    while (queue.size) {\n      const currentNode = queue.dequeue();\n      yield currentNode;\n      if (currentNode.left !== null) {\n        queue.enqueue(currentNode.left);\n      }\n      if (currentNode.right !== null) {\n        queue.enqueue(currentNode.right);\n      }\n    }\n  }\n  \n  /**\n   * Generates an iterator for traversing the binary tree in pre-order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {Generator<BTNode<K, V>, void, void>} The iterator for pre-order traversal.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   */\n  private static *preOrderIterator<K extends Key, V>(root: BTNode<K, V> | null): Generator<BTNode<K, V>, void, void> {\n    if (root !== null) {\n      yield root;\n      // @ts-ignore\n      yield* TraversalHelper.preOrderIterator(root.left);\n      // @ts-ignore\n      yield* TraversalHelper.preOrderIterator(root.right);\n    }\n  }\n  \n  /**\n   * Generates an iterator for traversing the binary tree in in-order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {Generator<BTNode<K, V>, void, void>} The iterator for in-order traversal.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  private static *inOrderIterator<K extends Key, V>(root: BTNode<K, V> | null): Generator<BTNode<K, V>, void, void> {\n    if (root !== null) {\n      // @ts-ignore\n      yield* TraversalHelper.inOrderIterator(root.left);\n      yield root;\n      // @ts-ignore\n      yield* TraversalHelper.inOrderIterator(root.right);\n    }\n  }\n  \n  /**\n   * Generates an iterator for traversing the binary tree in post-order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V> | null} root - The root node of the binary tree.\n   * @returns {Generator<BTNode<K, V>, void, void>} The iterator for post-order traversal.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  private static *postOrderIterator<K extends Key, V>(root: BTNode<K, V> | null): Generator<BTNode<K, V>, void, void> {\n    if (root !== null) {\n      // @ts-ignore\n      yield* TraversalHelper.postOrderIterator(root.left);\n      // @ts-ignore\n      yield* TraversalHelper.postOrderIterator(root.right);\n      yield root;\n    }\n  }\n}","import {CompareHelper} from \"../helper/compare\";\nimport {BTNode} from '../node/node';\nimport {TraversalHelper} from '../helper/traversal';\nimport {CalcHelper} from '../helper/calc';\n\nimport {TraversalOrder} from '@/enums/binary-tree/index';\nimport {Key, MatchFn, TraversalFn} from '@/types/binary-tree/index';\n\n/**\n * Represents an abstract base class for a binary tree structure with generic data.\n * @template K - The type of the keys (number or string) stored in the binary tree nodes.\n * @template V - The type of the value stored in the binary tree nodes.\n */\nexport abstract class BinaryTreeBase<K extends Key = number, V = any> {\n  protected _root: BTNode<K, V> |  null;\n  protected _size: number\n  \n  protected constructor() {\n    this._root = null;\n    this._size = 0;\n  }\n  \n  /**\n   * Gets the root node of the binary tree.\n   * @returns {BTNode<K, V> | null} - The root node of the binary tree.\n   */\n  get root(): BTNode<K, V> | null {\n    return this._root;\n  }\n  \n  /**\n   * Gets the number of nodes in the binary tree.\n   * @returns {number} - The size of the binary tree.\n   */\n  get size(): number {\n    return this._size;\n  }\n  \n  /**\n   * Checks if the binary tree is empty.\n   * @returns {boolean} - `true` if the binary tree is empty, `false` otherwise.\n   */\n  get isEmpty(): boolean {\n    return this._size === 0;\n  }\n  abstract get(key: K, order?: TraversalOrder): V | undefined\n  abstract has(key: K, order?: TraversalOrder): boolean\n  abstract set(key: K, val: V, order?: TraversalOrder): boolean\n  abstract node(key: K): BTNode<K, V> | null\n  abstract add(key: K, val: V): void\n  abstract delete(key: K): void\n  \n  /**\n   * Iterates over each node in the binary tree, in a specified order and applies a callback function.\n   * @param {TraversalFn<K, V>} traversalFn - The callback function to apply to each node.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {void}\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  forEach(traversalFn: TraversalFn<K, V>, order?: TraversalOrder): void {\n    TraversalHelper.forEach<K, V>(this.root, traversalFn, order);\n  }\n  \n  /**\n   * Finds a node in the binary tree that matches a given condition using the specified traversal order.\n   * @param {MatchFn<K, V>} matchFn - The condition to match nodes.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {BTNode<K, V> | null} - The first node that matches the condition, or `null` if not found.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  findNode(matchFn: MatchFn<K, V>, order?: TraversalOrder): BTNode<K, V> | null {\n    return TraversalHelper.findNode<K, V>(this.root, matchFn, order)\n  }\n  \n  /**\n   * Finds the value in the binary tree that matches a given condition using the specified traversal order.\n   * @param {MatchFn<K, V>} matchFn - The condition to match values.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {V | undefined} - The first value that matches the condition, or `undefined` if not found.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  findValue(matchFn: MatchFn<K, V>, order?: TraversalOrder): V | undefined {\n    return TraversalHelper.findValue(this.root, matchFn, order);\n  }\n  \n  /**\n   * Checks if any node in the binary tree matches a given condition using the specified traversal order.\n   * @param {MatchFn<K, V>} matchFn - The condition to match nodes.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {boolean} - `true` if at least one node matches the condition, `false` otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  some(matchFn: MatchFn<K, V>, order?: TraversalOrder): boolean {\n    return TraversalHelper.some<K, V>(this.root, matchFn, order);\n  }\n  \n  /**\n   * Checks if all nodes in the binary tree match a given condition using the specified traversal order.\n   * @param {MatchFn<K, V>} matchFn - The condition to match nodes.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {boolean} - `true` if all nodes match the condition, `false` otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  every(matchFn: MatchFn<K, V>, order?: TraversalOrder): boolean {\n    return TraversalHelper.every<K, V>(this.root, matchFn, order);\n  }\n  \n  /**\n   * Clears the binary tree, removing all nodes.\n   * @returns {void}\n   *\n   * @timecomplexity O(1)\n   * @spacecomplexity O(1)\n   */\n  clear(): void {\n    this.setRoot(null);\n    this.setSize(0);\n  }\n  \n  /**\n   * Gets the maximum depth of the binary tree.\n   * @returns {number} - The maximum depth of the binary tree.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  maxDepth(): number {\n    return CalcHelper.maxDepth(this.root);\n  }\n  \n  /**\n   * Checks if the binary tree is equal to another tree by comparing their structures.\n   * @param {BTNode<K, V> | null} root - The root of the other binary tree.\n   * @returns {boolean} - `true` if the binary trees are equal,\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  isEqual(root: BTNode<K, V> | null): boolean {\n    return CompareHelper.isEqual<K, V>(this.root, root);\n  }\n  \n  /**\n   * Checks if the binary tree is perfect.\n   * A binary tree is considered perfect if all nodes have exactly two children, and all leaf nodes are at the same level.\n   * @returns {boolean} True if the tree is perfect, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  isPerfect(): boolean {\n    return CompareHelper.isPerfect(this.root);\n  }\n  \n  /**\n   * Checks if the binary tree is full.\n   * A binary tree is considered full if each node has either 0 or 2 children.\n   * @returns {boolean} - True if the binary tree is full, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  isFull(): boolean {\n    return CompareHelper.isFull<K, V>(this.root)\n  }\n  \n  /**\n   * Checks if the binary tree is complete.\n   * A binary tree is considered complete if all levels, except possibly the last,\n   * are completely filled, and all nodes are as left as possible.\n   * @returns {boolean} - True if the binary tree is complete, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   */\n  isComplete(): boolean {\n    return CompareHelper.isComplete<K, V>(this.root)\n  }\n  \n  /**\n   * Checks if the binary tree is balanced.\n   * A binary tree is considered balanced if the height of the two subtrees of any node\n   * never differs by more than one.\n   * @returns {boolean} - True if the binary tree is balanced, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(h), where h is the height of the binary tree.\n   */\n  isBalanced(): boolean {\n    return CompareHelper.isBalanced<K, V>(this.root)\n  }\n  \n  /**\n   * Generates an iterator for the keys in the binary tree using the specified traversal order.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {Generator<K, void, void>} - An iterator for the keys in the binary tree.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  *keys(order?: TraversalOrder): Generator<K, void, void> {\n    // @ts-ignore\n    for (const node of TraversalHelper.getIterator<K, V>(this.root, order)) {\n      yield node.key\n    }\n  }\n  \n  /**\n   * Generates an iterator for the values in the binary tree using the specified traversal order.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {Generator<V, void, void>} - An iterator for the values in the binary tree.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  *values(order?: TraversalOrder): Generator<V, void, void> {\n    // @ts-ignore\n    for (const node of TraversalHelper.getIterator<K, V>(this.root, order)) {\n      yield node.val\n    }\n  }\n  \n  /**\n   * Generates an iterator for the entries (key-value pairs) in the binary tree using the specified traversal order.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {Generator<[K, V], void, void>} - An iterator for the entries in the binary tree.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  *entries(order?: TraversalOrder): Generator<[K, V], void, void> {\n    // @ts-ignore\n    for (const node of TraversalHelper.getIterator<K, V>(this.root, order)) {\n      yield [node.key, node.val]\n    }\n  }\n  \n  /**\n   * Generates an iterator for the nodes in the binary tree using the specified traversal order.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {Generator<BTNode<K, V>, void, void>} - An iterator for the nodes in the binary tree.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  *nodes(order?: TraversalOrder): Generator<BTNode<K, V>, void, void> {\n    // @ts-ignore\n    for (const node of TraversalHelper.getIterator<K, V>(this.root, order)) {\n      yield node\n    }\n  }\n  protected setRoot(root: BTNode<K, V> | null): void {\n    this._root = root;\n  }\n  protected setSize(number: number): void {\n    this._size = number;\n  }\n}","import {Key} from \"@/types/binary-tree/index\";\n\n/**\n * Represents a node in a binary tree.\n * @template K - The type of the key (number or string).\n * @template V - The type of the value stored in the node.\n */\nexport class BTNode<K extends Key, V> {\n  key: K\n  val: V\n  left: BTNode<K, V> | null\n  right: BTNode<K, V> | null\n  /**\n   * Creates a new instance of the BTNode class.\n   * @param {K} key - The key associated with the node.\n   * @param {V} val - The value associated with the node.\n   */\n  constructor(key: K, val: V) {\n    this.key = key\n    this.val = val;\n    this.left = null;\n    this.right = null\n  }\n}","import Queue from '../../queue/queue';\nimport {Entries, Key} from '@/types/binary-tree';\nimport {BTNode} from '../node/node';\nimport {TraversalHelper} from './traversal';\n\nimport {TraversalOrder} from '@/enums/binary-tree';\n\n/**\n * Helper class for mutating a binary tree.\n */\nexport class BTMutationHelper {\n  /**\n   * Adds a new node with the given key and value to the binary tree using level-order (BFS) traversal for insertion.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V>} root - The root node of the binary tree.\n   * @param {K} key - The key of the new node to be added.\n   * @param {V} val - The value of the new node to be added.\n   * @returns {[BTNode<K, V>, boolean]} - Returns a tuple with the updated root node and a boolean indicating success.\n   *                                   The boolean is true if the node was successfully added, false otherwise.\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   * @description\n   * This method adds a new node with the given key and value to the binary tree.\n   * If the tree is empty, the new node becomes the root. Otherwise, it adds the node to the first\n   * available position using level order traversal.\n   */\n  static add<K extends Key, V>(root: BTNode<K, V>, key: K, val: V): [BTNode<K, V>, boolean] {\n    const newNode = new BTNode(key, val);\n    \n    if (root === null) {\n      return [newNode, true];\n    }\n    // @ts-ignore\n    for (const n of TraversalHelper.getIterator<K, V>(root, TraversalOrder.LevelOrder)) {\n      if (n.left === null) {\n        n.left = newNode;\n        return [root, true];\n      }\n      if (n.right === null) {\n        n.right = newNode;\n        return [root, true];\n      }\n    }\n  }\n  \n  /**\n   * Adds multiple entries to a binary tree in a breadth-first manner.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V>} [root=null] - The root of the binary tree. If not provided, a new tree will be created.\n   * @param {Entries<K, V>} entries - The array of entries to add to the binary tree.\n   * @returns {[BTNode<K, V>, number]} - A tuple containing the root of the modified binary tree and the number of nodes added.\n   *\n   * @timecomplexity O(n), where n is the total number of nodes (both existing nodes in the tree and the nodes to be added).\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   * @description\n   * This method adds multiple entries to a binary tree using a breadth-first traversal approach.\n   * If the root is not provided, a new binary tree will be created. The entries are added level by level,\n   * filling the left child before moving to the right child. The method returns a tuple containing the root\n   * of the modified binary tree and the number of nodes added.\n   */\n  static addMany<K extends Key, V>(root: BTNode<K, V>, entries: Entries<K, V>): [BTNode<K, V>, number] {\n    let count: number = 0;\n    \n    if (entries.length === 0) {\n      return [root, count];\n    }\n    \n    const queue: Queue<BTNode<K, V>> = new Queue();\n    let index = 0;\n    \n    if (root === null) {\n      root = new BTNode(...entries[index]);\n      index++;\n      count++\n    }\n    \n    queue.enqueue(root);\n    \n    while (index < entries.length && queue.size > 0) {\n      const currentNode = queue.dequeue();\n      \n      if (currentNode.left === null) {\n        currentNode.left = new BTNode(...entries[index]);\n        index++;\n        count++\n      }\n      \n      queue.enqueue(currentNode.left);\n      \n      if (index < entries.length && currentNode.right === null) {\n        currentNode.right = new BTNode(...entries[index]);\n        index++;\n        count++\n      }\n      \n      queue.enqueue(currentNode.right);\n    }\n    \n    return [root, count];\n  }\n  \n  /**\n   * Sets the value of the node with the specified key in the binary tree using the specified traversal order.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V>} [root=null] - The root of the binary tree\n   * @param {K} key - The key of the node to be updated.\n   * @param {V} val - The new value for the node.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {boolean} - `true` if the node with the given key was found and updated, `false` otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   * @description This method sets the value of the node with the specified key in the binary tree.\n   * It uses a specified traversal order to find the node.\n   */\n  static set<K extends Key, V>(root: BTNode<K, V>, key: K, val: V, order?: TraversalOrder): boolean {\n    const node = TraversalHelper.findNode<K, V>(root, (_v, k) => k === key, order);\n    if (node !== null) {\n      node.val = val;\n      return true;\n    }\n    return false\n  }\n  \n  /**\n   * Deletes a node with the specified key from a binary tree.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {BTNode<K, V>} root - The root node of the binary tree.\n   * @param {K} key - The key of the node to be deleted.\n   * @returns {[BTNode<K, V> | null, boolean]} - Returns a tuple with the updated root node and a boolean indicating success.\n   *                                           The boolean is true if the node was successfully deleted, false otherwise.\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   * @description This method deletes the node with the specified key from the binary tree.\n   * It replaces the node with the deepest rightmost node and then removes the deepest rightmost node.\n   */\n  static delete<K extends Key, V>(root: BTNode<K, V>, key: K): [BTNode<K, V> | null, boolean] {\n    if (root === null) {\n      return [null, false];\n    }\n    \n    if (root.left === null && root.right === null && root.key === key) {\n      return [null, true];\n    }\n    \n    let keyNode: BTNode<K, V> | null = null;\n    let parentDeepestRightMostNode: BTNode<K, V> | null = null;\n    let deepestRightMostNode: BTNode<K, V> | null = null;\n    \n    // Traverse the tree in level order to find the node with the specified key and the deepest rightmost node.\n    // @ts-ignore\n    for (const n of TraversalHelper.getIterator<K, V>(root, TraversalOrder.LevelOrder)) {\n      if (n.key === key){\n        keyNode = n\n      }\n      if (n.left !== null || n.right !== null) {\n        parentDeepestRightMostNode = n;\n      }\n      deepestRightMostNode = n;\n    }\n    \n    // If the node with the specified key is not found, return false.\n    if (!keyNode) {\n      return [root, false];\n    }\n    \n    // Replace the key node with the deepest node (if they are different)\n    if (deepestRightMostNode !== keyNode) {\n      keyNode.key = deepestRightMostNode.key;\n      keyNode.val = deepestRightMostNode.val;\n    }\n    \n    // Disconnect the deepest node from its parent\n    if (parentDeepestRightMostNode.left === deepestRightMostNode) {\n      parentDeepestRightMostNode.left = null;\n    } else if (parentDeepestRightMostNode.right === deepestRightMostNode) {\n      parentDeepestRightMostNode.right = null;\n    }\n    \n    return [root, true];\n  }\n}","import {TraversalOrder} from '../../enums/binary-tree/index';\nimport {Entries, Key} from '../../types/binary-tree/index';\nimport {BinaryTreeBase} from './base/binary-tree-base';\nimport {CalcHelper} from \"./helper/calc\";\nimport {BTNode} from './node/node';\nimport {BTMutationHelper} from './helper/bt-mutation';\n\n/**\n * Represents a binary tree.\n *\n * @extends {BinaryTreeBase<K, V>}\n * @template K - The type of the keys (number or string) stored in the binary tree nodes.\n * @template V - The type of the value stored in the binary tree nodes.\n */\nexport default class BinaryTree<K extends Key = number, V = any> extends BinaryTreeBase<K, V>{\n  /**\n   * Constructs a new instance of the BinaryTree class.\n   * @param {BTNode<K, V> | null} [root] - The root node of the binary tree.\n   *                                       If not provided, the tree will be initialized as empty.\n   * @param {number} [size] - The size of the binary tree.\n   *                          If not provided, the size will be calculated based on the root node.\n   */\n  constructor(root?: BTNode<K, V> | null, size?: number) {\n    super();\n    if (root) {\n      this.setRoot(root);\n      this.setSize(size ?? CalcHelper.calcSize<K, V>(root));\n    }\n  }\n  \n  /**\n   * Creates a new BinaryTree instance from an array of entries using level-order (BFS) traversal for insertion.\n   * @template K - The type of the key (number or string).\n   * @template V - The type of the value stored in the node.\n   * @param {Entries<K, V>} entries - The entries to initialize the binary tree.\n   * @returns {BinaryTree<K, V>} - A new binary tree instance.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   */\n  static fromEntries<K extends Key, V>(entries: Entries<K, V>): BinaryTree<K, V> {\n    const [root, count] = BTMutationHelper.addMany<K, V>(null, entries);\n    return new BinaryTree(root, count);\n  }\n  \n  /**\n   * Gets the value associated with the specified key in the binary tree, employing the chosen traversal order.\n   * @param {number | string} key - The key to search for.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {V | undefined} - The value associated with the key, or undefined if not found.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  get(key: K, order?: TraversalOrder): V | undefined {\n    return this.findValue((_v, k) => k === key, order);\n  }\n  \n  /**\n   * Gets the node with the specified key in the binary tree, employing the chosen traversal order.\n   * @param {K} key - The key to search for.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {BTNode<K, V>} - The node with the specified key.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  node(key: K, order?: TraversalOrder): BTNode<K, V> {\n    return this.findNode((_v, k) => k === key, order);\n  }\n  \n  /**\n   * Checks if the binary tree contains a node with the specified key, employing the chosen traversal order.\n   * @param {K} key - The key to check for.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {boolean} - True if the binary tree contains a node with the specified key, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  has(key: K, order?: TraversalOrder): boolean {\n    return this.some((_v, k) => k === key, order);\n  }\n  \n  /**\n   * Sets the value associated with the specified key in the binary tree, employing the chosen traversal order.\n   * @param {K} key - The key to set.\n   * @param {V} val - The value to associate with the key.\n   * @param {TraversalOrder} [order] - The order of traversal (default: InOrder).\n   * @returns {boolean} - True if the key was successfully set, false otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity\n   * - O(h) for depth-first traversals, where h is the height of the binary tree.\n   * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree.\n   */\n  set(key: K, val: V, order?: TraversalOrder): boolean {\n    return BTMutationHelper.set<K, V>(this.root, key, val, order);\n  }\n  \n  /**\n   * Adds a new node with the given key and value to the binary tree, employing level-order (BFS) traversal for insertion.\n   * @param {K} key - The key of the new node.\n   * @param {V} val - The value of the new node.\n   * @returns {void}\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   */\n  add(key: K, val: V): void {\n    const [root, isSuccess] = BTMutationHelper.add<K, V>(this.root, key, val);\n    if (isSuccess) {\n      this.setRoot(root);\n      this.setSize(this.size + 1);\n    }\n  }\n  \n  /**\n   * Adds multiple nodes with the given keys and values to the binary tree, employing level-order (BFS) traversal for insertion.\n   * @param {Entries<K, V>} entries - An array of key-value pairs to be added to the binary tree.\n   * @returns {void}\n   *\n   * @timecomplexity O(n), where n is the total number of nodes (both existing nodes in the tree and the nodes to be added).\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   */\n  addMany(entries: Entries<K, V>): void {\n    const [root, count] = BTMutationHelper.addMany<K, V>(this.root, entries);\n    if (count > 0) {\n      this.setRoot(root);\n      this.setSize(this.size + count);\n    }\n  }\n  \n  /**\n   * Deletes the node with the specified key from the binary tree.\n   * It replaces the node with the deepest rightmost node and then removes the deepest rightmost node.\n   * @param {K} key - The key of the node to be deleted.\n   * @returns {boolean} - `true` if the node with the given key was found and deleted, `false` otherwise.\n   *\n   * @timecomplexity O(n), where n is the number of nodes in the binary tree.\n   * @spacecomplexity O(w), where w is the maximum width of the binary tree.\n   */\n  delete(key: K): boolean {\n    const [root, isSuccess] = BTMutationHelper.delete<K, V>(this.root, key);\n    if (isSuccess) {\n      this.setRoot(root);\n      this.setSize(this.size - 1);\n    }\n    return isSuccess;\n  }\n}","import {BSTComparator, Entries, Key} from \"@/types/binary-tree/index\";\nimport {BTNode} from \"@/data-structures/binary-tree/node/node\";\n\nexport const numericCompare: BSTComparator<number> = (a, b) => a - b;\nexport const strCompare: BSTComparator<string> = (a, b) => a.localeCompare(b, undefined, { sensitivity: 'base' });\n\n/**\n * Helper class for Binary Search Tree operations.\n */\nexport class BSTHelper {\n  /**\n   * Get the value associated with a key in the BST.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {BTNode<K, V>} root - Root node of the BST\n   * @param {K} key - Key to search for\n   * @param {BSTComparator<K>} comparator - Function to compare keys\n   * @returns {V | undefined} - Value associated with the key, or undefined if not found\n   \n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  static get<K extends Key, V>(root: BTNode<K, V>, key: K, comparator: BSTComparator<K>): V | undefined {\n    return BSTHelper.node<K, V>(root, key, comparator)?.val;\n  }\n  \n  /**\n   * Get the node associated with a key in the BST.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {BTNode<K, V>} root - Root node of the BST\n   * @param {K} key - Key to search for\n   * @param {BSTComparator<K>} comparator - Function to compare keys\n   * @returns {BTNode<K, V> | null} - Node associated with the key, or null if not found\n   \n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  static node<K extends Key, V>(root: BTNode<K, V>, key: K, comparator: BSTComparator<K>): BTNode<K, V> | null {\n    if (root === null) {\n      return null;\n    }\n    \n    const compareResult = comparator(key, root.key);\n    \n    if (compareResult === 0) {\n      return root;\n    }\n    if (compareResult < 0) {\n      return BSTHelper.node(root.left, key, comparator);\n    }\n    return BSTHelper.node(root.right, key, comparator);\n  }\n  \n  /**\n   * Check if a key exists in the BST.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {BTNode<K, V>} root - Root node of the BST\n   * @param {K} key - Key to search for\n   * @param {BSTComparator<K>} comparator - Function to compare keys\n   * @returns {boolean} - True if the key exists, false otherwise\n   \n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  static has<K extends Key, V>(root: BTNode<K, V>, key: K, comparator: BSTComparator<K>): boolean {\n    return !!BSTHelper.node<K, V>(root, key, comparator);\n  }\n  \n  /**\n   * Create a balanced BST from sorted entries.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {Entries<K, V>} entries - Array of entries sorted by key\n   * @param {number} start - Start index of the current range\n   * @param {number} end - End index of the current range\n   * @returns {BTNode<K, V> | null} - Root node of the resulting BST\n  \n   * @timecomplexity O(n) - Linear time complexity as it visits each entry once.\n   * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function.\n   */\n  static fromSortedEntries<K extends Key, V>(entries: Entries<K, V>, start: number, end: number ): BTNode<K, V> | null {\n    if (start > end) {\n      return null;\n    }\n    \n    const mid = Math.floor((start + end) / 2);\n    const node = new BTNode<K, V>(...entries[mid]);\n    \n    node.left = BSTHelper.fromSortedEntries<K, V>(entries, start, mid - 1);\n    node.right = BSTHelper.fromSortedEntries<K, V>(entries, mid + 1, end);\n    return node;\n  }\n  \n  /**\n   * Set the value associated with a key in the BST.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {BTNode<K, V>} root - Root node of the BST\n   * @param {K} key - Key to set the value for\n   * @param {V} val - Value to set\n   * @param {BSTComparator<K>} comparator - Function to compare keys\n   * @returns {boolean} - True if the key was found and value set, false otherwise\n   \n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  static set<K extends Key, V>(root: BTNode<K, V>, key: K, val: V, comparator: BSTComparator<K>): boolean {\n    const node = BSTHelper.node<K, V>(root, key, comparator);\n    if (node !== null) {\n      node.val = val;\n      return true;\n    }\n    return false;\n  }\n  \n  /**\n   * Add a new node with the given key and value to the BST.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {BTNode<K, V>} root - Root node of the BST\n   * @param {K} key - Key to add\n   * @param {V} val - Value to associate with the key\n   * @param {BSTComparator<K>} comparator - Function to compare keys\n   * @returns {[BTNode<K, V>, boolean]} - Tuple containing the root of the updated BST and a boolean indicating success\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function.\n   */\n  static add<K extends Key, V>(root: BTNode<K, V>, key: K, val: V, comparator: BSTComparator<K>): [BTNode<K, V>, boolean] {\n    if (root === null) {\n      return [new BTNode<K, V>(key, val), true];\n    }\n    \n    const compareResult = comparator(key, root.key);\n    \n    if (compareResult < 0) {\n      const [node, isSuccess] = BSTHelper.add(root.left, key, val, comparator);\n      root.left = node;\n      return [root, isSuccess];\n    } else if (compareResult > 0) {\n      const [node, isSuccess] = BSTHelper.add(root.right, key, val, comparator);\n      root.right = node;\n      return [root, isSuccess];\n    } else {\n      console.warn('Duplicate key, do not added')\n      return [root, false];\n    }\n  }\n  \n  /**\n   * Delete a node with the given key from the BST.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {BTNode<K, V> | null} root - Root node of the BST\n   * @param {K} key - Key to delete\n   * @param {BSTComparator<K>} comparator - Function to compare keys\n   * @param {boolean} deleted - Flag indicating whether a node has already been deleted\n   * @returns {[BTNode<K, V> | null, boolean]} - Tuple containing the root of the updated BST and a boolean indicating success\n  \n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function.\n   */\n  static delete<K extends Key, V>(root: BTNode<K, V> | null, key: K, comparator: BSTComparator<K>, deleted: boolean = false): [BTNode<K, V> | null, boolean] {\n    if (root === null) {\n      return [null, deleted];\n    }\n    \n    const comparisonResult = comparator(key, root.key);\n    \n    if (comparisonResult < 0) {\n      const [left,isDeleted ] = BSTHelper.delete(root.left, key, comparator, deleted)\n      deleted = isDeleted;\n      root.left = left;\n    } else if (comparisonResult > 0) {\n      const [right, isDeleted] = BSTHelper.delete(root.right, key, comparator, deleted)\n      deleted = isDeleted;\n      root.right = right;\n    } else {\n      // Node to be deleted found\n      deleted = true;\n      \n      // Case 1: Node with only one child or no child\n      if (root.left === null) {\n        return [root.right, deleted];\n      } else if (root.right === null) {\n        return [root.left, deleted];\n      }\n      \n      // Case 3: Node with two children\n      const successor = BSTHelper.mostLeft(root.right);\n      \n      root.key = successor.key\n      root.val = successor.val\n      \n      const [right] = BSTHelper.delete(root.right, root.key, comparator, deleted);\n      root.right = right;\n    }\n    \n    return [root, deleted];\n  }\n  \n  /**\n   * Find the leftmost node in the BST.\n   * @template K - Key type\n   * @template V - Value type\n   * @param {BTNode<K, V> | null} root - Root node of the BST\n   * @returns {BTNode<K, V> | null} - The leftmost node in the BST\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through the left side of a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  private static mostLeft<K extends Key, V>(root: BTNode<K, V> | null): BTNode<K, V> | null {\n    let currentNode = root;\n    \n    while (currentNode && currentNode?.left !== null) {\n      currentNode = currentNode.left;\n    }\n    return currentNode;\n  }\n}","import {BSTComparator, Entries, Key} from '@/types/binary-tree/index';\nimport {BinaryTreeBase} from './base/binary-tree-base';\nimport {BSTHelper, numericCompare} from './helper/bst';\nimport {CalcHelper} from './helper/calc';\nimport {BTNode} from \"./node/node\";\n\n/**\n * Represents a binary search tree.\n * @template K - The type of the keys (number or string) stored in the binary tree nodes.\n * @template V - The type of the value stored in the binary tree nodes.\n */\nexport default class BinarySearchTree<K extends Key = number, V = any> extends BinaryTreeBase<K, V>{\n  private readonly comparator: BSTComparator<K>\n  \n  /**\n   * Constructor for BinarySearchTree.\n   * @param {BSTComparator<K>} [comparator] - The comparator function for keys of the binary search tree.\n   *                                          If not provided, the default comparator is (a, b) => a - b.\n   * @param {BTNode<K, V> | null} [bstRoot] - The root node of the binary search tree.\n   *                                          If not provided, the tree will be initialized as empty.\n   * @param {number} [size] - The size of the binary search tree.\n   *                          If not provided, the size will be calculated based on the root node.\n   */\n  constructor(comparator?: BSTComparator<K>, bstRoot?: BTNode<K, V>, size?: number) {\n    super()\n    this.comparator = comparator || numericCompare as BSTComparator<K>;\n    if (bstRoot) {\n      this.setRoot(bstRoot);\n      this.setSize(size ?? CalcHelper.calcSize<K, V>(bstRoot));\n    }\n  }\n  \n  /**\n   * Create a BinarySearchTree from an array of entries.\n   * @template K - The type of the keys (number or string) stored in the binary tree nodes.\n   * @template V - The type of the value stored in the binary tree nodes.\n   * @param {Entries<K, V>} entries - Array of key-value entries.\n   * @param {BSTComparator<K>} [comparator] - The comparator function for keys of the binary search tree.\n   *                                          If not provided, the default comparator is (a, b) => a - b.\n   * @returns {BinarySearchTree<K, V>} - BinarySearchTree instance.\n   * @timecomplexity O(n log n) - Time complexity of adding many entries individually is O(n log n)\n   * @spacecomplexity O(n) - Linear space complexity as each entry creates a node in the tree.\n   */\n  static fromEntries<K extends Key = number, V = any>(entries: Entries<K, V>, comparator?: BSTComparator<K>): BinarySearchTree<K, V> {\n    const bst= new BinarySearchTree<K, V>(comparator);\n    bst.addMany(entries);\n    return bst;\n  }\n  \n  /**\n   * Create a BinarySearchTree from an array of sorted entries.\n   * @template K - The type of the keys (number or string) stored in the binary tree nodes.\n   * @template V - The type of the value stored in the binary tree nodes.\n   * @param {Entries<K, V>} entries - Array of key-value entries.\n   * @param {BSTComparator<K>} [comparator] - The comparator function for keys of the binary search tree.\n   *                                          If not provided, the default comparator is (a, b) => a - b.\n   * @returns {BinarySearchTree<number, V>} - BinarySearchTree instance.\n   * @timecomplexity O(n) - Linear time complexity, where n is the number of numeric entries.\n   * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function.\n   */\n  static fromSortedEntries<K extends Key, V>(entries: Entries<K, V>, comparator?: BSTComparator<K>): BinarySearchTree<K, V> {\n    const bstRoot = BSTHelper.fromSortedEntries<K, V>(entries, 0, entries.length - 1)\n    const size = entries.length;\n    if (bstRoot) {\n      return new BinarySearchTree<K, V>(comparator, bstRoot, size);\n    }\n  }\n  \n  /**\n   * Get the value associated with a key in the BST.\n   * @param {K} key - Key to search for.\n   * @returns {V | undefined} - Value associated with the key, or undefined if not found.\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  get(key: K): V | undefined {\n    return BSTHelper.get<K, V>(this.root, key, this.comparator);\n  }\n  \n  /**\n   * Get the node associated with a key in the BST.\n   * @param {K} key - Key to search for.\n   * @returns {BTNode<K, V> | null} - Node associated with the key, or null if not found.\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  node(key: K): BTNode<K, V> | null {\n    return BSTHelper.node<K, V>(this.root, key, this.comparator);\n  }\n  \n  /**\n   * Check if a key exists in the BST.\n   * @param {K} key - Key to check.\n   * @returns {boolean} - True if the key exists, false otherwise.\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  has(key: K): boolean {\n    return BSTHelper.has<K, V>(this.root, key, this.comparator);\n  }\n  \n  /**\n   * Add a new node with the given key and value to the BST.\n   * @param {K} key - Key to add.\n   * @param {V} val - Value to associate with the key.\n   * @returns {boolean} - True if the node was added successfully, false if the key already exists.\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function.\n   */\n  add(key: K, val: V): boolean {\n    const [root, isSuccess] = BSTHelper.add<K, V>(this.root, key, val, this.comparator);\n    if (isSuccess) {\n      this.setRoot(root);\n      this.setSize(this.size + 1)\n    }\n    return isSuccess;\n  }\n  \n  /**\n   * Adds multiple nodes with the given keys and values to the BST.\n   * @param {Entries<K, V>} entries - Array of key-value entries to add.\n   * @returns {number} - Number of entries successfully added.\n   * @timecomplexity O(n log n) - Time complexity of adding many entries individually is O(n log n)\n   * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function.\n   */\n  addMany(entries: Entries<K, V>): number {\n    let count: number = 0;\n    for (let [key, val] of entries) {\n      count = this.add(key, val) ? count + 1 : count;\n    }\n    return count;\n  }\n  \n  /**\n   * Set the value associated with a key in the BST.\n   * @param {K} key - Key to set the value for\n   * @param {V} val - Value to set\n   * @returns {boolean} - True if the key was found and value set, false otherwise\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size.\n   */\n  set(key: K, val: V): boolean {\n    return BSTHelper.set(this.root, key, val, this.comparator);\n  }\n  \n  /**\n   * Delete a node with the given key from the BST using InOrder successor.\n   * @param {K} key - Key to delete.\n   * @returns {boolean} - True if the node was successfully deleted, false if the key was not found.\n   * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree.\n   * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function.\n   */\n  delete(key: K): boolean {\n    const [root, isDeleted] = BSTHelper.delete<K, V>(this.root, key, this.comparator);\n    if (isDeleted) {\n      this.setRoot(root);\n      this.setSize(this.size - 1)\n    }\n    return isDeleted;\n  }\n}"],"mappings":"4ZAAA,IAAAA,EAAA,GAAAC,EAAAD,EAAA,YAAAE,EAAA,qBAAAC,EAAA,eAAAC,EAAA,qBAAAC,EAAA,UAAAC,EAAA,qBAAAC,EAAA,UAAAC,EAAA,mBAAAC,EAAA,mBAAAC,EAAA,eAAAC,IAAA,eAAAC,EAAAZ,GCKO,IAAea,EAAf,KAA4B,CAGnC,EAOsBC,EAAf,KAAoC,CAC/B,MACA,MACA,QAEA,aAAc,CACtB,KAAK,MAAQ,KACb,KAAK,MAAQ,KACb,KAAK,QAAU,CACjB,CAMA,IAAI,MAAiB,CACnB,OAAO,KAAK,KACd,CAMA,IAAI,MAAiB,CACnB,OAAO,KAAK,KACd,CAMA,IAAI,MAAe,CACjB,OAAO,KAAK,OACd,CAMA,IAAI,SAAmB,CACrB,OAAO,KAAK,OAAS,CACvB,CA6EA,OAAc,CACZ,KAAK,MAAQ,KACb,KAAK,MAAQ,KACb,KAAK,QAAU,CACjB,CAOU,aAAaC,EAAwB,CAC7C,OAAOA,GAAS,GAAKA,EAAQ,KAAK,OACpC,CACF,EC7IO,IAAMC,EAAN,cAAyBC,CAAqB,CACnD,IACA,KACA,YAAYC,EAAQ,CAClB,MAAM,EACN,KAAK,IAAMA,EACX,KAAK,KAAO,IACd,CACF,EAMqBC,EAArB,MAAqBC,UAA4BC,CAA8B,CAC7E,aAAc,CACZ,MAAM,CACR,CASA,OAAO,UAAaC,EAAgC,CAClD,IAAMC,EAAO,IAAIH,EAEjB,QAAWI,KAAQF,EACjBC,EAAK,KAAKC,CAAI,EAGhB,OAAOD,CACT,CASA,KAAKL,EAA6B,CAChC,IAAMO,EAAU,IAAIT,EAAQE,CAAG,EAE/B,OAAI,KAAK,SACP,KAAK,MAAQO,EACb,KAAK,MAAQA,IAEb,KAAK,MAAO,KAAOA,EACnB,KAAK,MAAQA,GAGf,KAAK,UAEE,IACT,CAQA,KAAqB,CACnB,GAAI,KAAK,QAAU,KACjB,OAGF,GAAI,KAAK,QAAU,KAAK,MAAO,CAC7B,IAAMP,EAAM,KAAK,MAAM,IACvB,YAAK,MAAQ,KACb,KAAK,MAAQ,KACb,KAAK,UAEEA,CACT,CAEA,IAAIQ,EAAc,KAAK,MAEvB,KAAOA,EAAY,OAAS,KAAK,OAC/BA,EAAcA,EAAY,KAG5BA,EAAY,KAAO,KACnB,IAAMR,EAAM,KAAK,MAAO,IACxB,YAAK,MAAQQ,EACb,KAAK,UAEER,CACT,CAQA,OAAuB,CACrB,GAAI,KAAK,QAAU,KACjB,OAGF,IAAMS,EAAc,KAAK,MAEzB,OAAI,KAAK,QAAU,KAAK,QACtB,KAAK,MAAQ,MAGf,KAAK,MAAQA,EAAY,KACzB,KAAK,UAEEA,EAAY,GACrB,CASA,QAAQT,EAA6B,CACnC,IAAMO,EAAU,IAAIT,EAAQE,CAAG,EAE/B,OAAI,KAAK,SACP,KAAK,MAAQO,EACb,KAAK,MAAQA,IAEbA,EAAQ,KAAO,KAAK,MACpB,KAAK,MAAQA,GAGf,KAAK,UAEE,IACT,CASA,GAAGG,EAA8B,CAC/B,IAAMF,EAAa,KAAK,OAAOE,CAAK,EAEpC,GAAIF,IAAgB,KAClB,OAAOA,EAAY,GAIvB,CASA,OAAOE,EAAkC,CACvC,GAAI,CAAC,KAAK,aAAaA,CAAK,EAC1B,OAAO,KAGT,IAAIF,EAAc,KAAK,MAEvB,QAASG,EAAY,EAAGA,EAAID,EAAOC,IACjCH,EAAcA,EAAa,KAG7B,OAAOA,CACT,CAUA,MAAME,EAAeV,EAAiB,CACpC,IAAMQ,EAAc,KAAK,OAAOE,CAAK,EAErC,OAAIF,IAAgB,MAClBA,EAAY,IAAMR,EACX,IAGF,EACT,CAUA,SAASU,EAAeV,EAAiB,CACvC,GAAIU,EAAQ,GAAKA,EAAQ,KAAK,QAC5B,MAAO,GAGT,GAAIA,IAAU,EACZ,MAAO,CAAC,CAAC,KAAK,QAAQV,CAAG,EAG3B,GAAIU,IAAU,KAAK,QACjB,MAAO,CAAC,CAAC,KAAK,KAAKV,CAAG,EAGxB,IAAMO,EAAU,IAAIT,EAAQE,CAAG,EAEzBY,EAAa,KAAK,OAAOF,EAAQ,CAAC,EAClCG,EAAYD,EAAY,KAE9B,OAAAA,EAAY,KAAOL,EACnBA,EAAQ,KAAOM,EAEf,KAAK,UAEE,EACT,CASA,SAASH,EAA8B,CACrC,GAAI,CAAC,KAAK,aAAaA,CAAK,EAC1B,OAGF,GAAIA,IAAU,EACZ,OAAO,KAAK,MAAM,EAGpB,GAAIA,IAAU,KAAK,QAAU,EAC3B,OAAO,KAAK,IAAI,EAGlB,IAAME,EAAa,KAAK,OAAOF,EAAQ,CAAC,EAExC,GAAIE,IAAe,KAAM,CACvB,IAAMH,EAAcG,EAAY,KAChC,OAAAA,EAAW,KAAOH,EAAa,KAC/B,KAAK,UAEEA,EAAa,GACtB,CAGF,CAOA,SAA+B,CAC7B,CAAC,KAAK,MAAO,KAAK,KAAK,EAAI,CAAC,KAAK,MAAO,KAAK,KAAK,EAElD,IAAID,EAAc,KAAK,MAEnBM,EACAC,EAA8B,KAElC,QAASJ,EAAI,EAAGA,EAAI,KAAK,QAASA,IAChCG,EAAWN,EAAa,KACxBA,EAAa,KAAOO,EACpBA,EAAWP,EACXA,EAAcM,EAGhB,OAAO,IACT,CASA,UAAUE,EAAgC,CACxC,GAAIA,EAAI,KAAK,UAAY,EAAG,OAAO,KAEnC,IAAMC,EAAWD,EAAI,EAAIA,EAAI,KAAK,QAAU,KAAK,QAAWA,EAAI,KAAK,QAEjER,EAAc,KAAK,MACnBO,EAAW,KAAK,MAEpB,KAAK,MAAO,KAAO,KAAK,MAExB,QAASJ,EAAI,EAAGA,EAAIM,EAAUN,IAC5BI,EAAWP,EACXA,EAAcA,EAAa,KAG7B,YAAK,MAAQA,EACb,KAAK,MAAQO,EAEb,KAAK,MAAO,KAAO,KAEZ,IACT,CAQA,SAAe,CACb,IAAMG,EAAW,CAAC,EACdV,EAAc,KAAK,MAEvB,KAAOA,GACLU,EAAI,KAAKV,EAAY,GAAG,EACxBA,EAAcA,EAAY,KAG5B,OAAOU,CACT,CACF,EC7UA,IAAMC,EAAN,cAAyBC,CAAsB,CAC7C,IACA,KACA,KACA,YAAYC,EAAQ,CAClB,MAAM,EACN,KAAK,IAAMA,EACX,KAAK,KAAO,KACZ,KAAK,KAAO,IACd,CACF,EAMqBC,EAArB,MAAqBC,UAA4BC,CAA6B,CAC5E,aAAc,CACZ,MAAM,CACR,CASA,OAAO,UAAaC,EAAgC,CAClD,IAAMC,EAAM,IAAIH,EAEhB,QAAWI,KAAQF,EACjBC,EAAK,KAAKC,CAAI,EAGhB,OAAOD,CACT,CASA,KAAKL,EAA6B,CAChC,IAAMO,EAAU,IAAIT,EAAWE,CAAG,EAElC,OAAI,KAAK,SACP,KAAK,MAAQO,EACb,KAAK,MAAQA,IAEb,KAAK,MAAM,KAAOA,EAClBA,EAAQ,KAAO,KAAK,MACpB,KAAK,MAAQA,GAGf,KAAK,UACE,IACT,CAQA,KAAqB,CACnB,GAAI,KAAK,QACP,OAGF,IAAMC,EAAa,KAAK,MAExB,OAAI,KAAK,QAAU,KAAK,OACtB,KAAK,MAAQ,KACb,KAAK,MAAQ,OAEb,KAAK,MAAQA,EAAY,KACzB,KAAK,MAAO,KAAO,MAGrB,KAAK,UACEA,EAAY,GACrB,CAQA,OAAuB,CACrB,GAAI,KAAK,QACP,OAGF,IAAMA,EAAc,KAAK,MAEzB,OAAI,KAAK,QAAU,KAAK,OACtB,KAAK,MAAQ,KACb,KAAK,MAAQ,OAEb,KAAK,MAAQA,EAAY,KACzB,KAAK,MAAO,KAAO,MAGrB,KAAK,UACEA,EAAY,GACrB,CASA,QAAQR,EAA6B,CACnC,IAAMO,EAAU,IAAIT,EAAWE,CAAG,EAElC,OAAI,KAAK,SACP,KAAK,MAAQO,EACb,KAAK,MAAQA,IAEbA,EAAQ,KAAO,KAAK,MACpB,KAAK,MAAO,KAAOA,EACnB,KAAK,MAAQA,GAGf,KAAK,UACE,IACT,CASA,GAAGE,EAA8B,CAC/B,IAAMC,EAAc,KAAK,OAAOD,CAAK,EAErC,GAAIC,IAAgB,KAClB,OAAOA,EAAY,GAIvB,CASA,OAAOD,EAAkC,CACvC,GAAIA,EAAQ,GAAKA,GAAS,KAAK,QAC7B,OAAO,KAGT,IAAIC,EACAC,EAGAF,GAAS,KAAK,QAAU,GAC1BC,EAAc,KAAK,MACnBC,EAAQF,IAERC,EAAc,KAAK,MACnBC,EAAQ,KAAK,QAAUF,EAAQ,GAGjC,IAAMG,EAAYH,GAAS,KAAK,QAAU,EAAI,OAAS,OAEvD,QAASI,EAAI,EAAGA,EAAIF,EAAOE,IACzBH,EAAcA,EAAaE,CAAS,EAGtC,OAAOF,CACT,CAUA,MAAMD,EAAeT,EAAiB,CACpC,IAAMU,EAAc,KAAK,OAAOD,CAAK,EAErC,OAAIC,IAAgB,MAClBA,EAAY,IAAMV,EACX,IAGF,EACT,CAUA,SAASS,EAAeT,EAAiB,CACvC,GAAIS,EAAQ,GAAKA,EAAQ,KAAK,QAC5B,MAAO,GAGT,GAAIA,IAAU,EACZ,MAAO,CAAC,CAAC,KAAK,QAAQT,CAAG,EAG3B,GAAIS,IAAU,KAAK,QACjB,MAAO,CAAC,CAAC,KAAK,KAAKT,CAAG,EAGxB,IAAMO,EAAU,IAAIT,EAAQE,CAAG,EACzBc,EAAa,KAAK,OAAOL,EAAQ,CAAC,EAClCM,EAAYD,EAAY,KAE9B,OAAAA,EAAY,KAAOP,EACnBQ,EAAW,KAAOR,EAElBA,EAAQ,KAAOO,EACfP,EAAQ,KAAOQ,EAEf,KAAK,UACE,EACT,CASA,SAASN,EAA8B,CACrC,GAAIA,EAAQ,GAAKA,GAAS,KAAK,QAC7B,OAGF,GAAIA,IAAU,EACZ,OAAO,KAAK,MAAM,EAGpB,GAAIA,IAAU,KAAK,QAAU,EAC3B,OAAO,KAAK,IAAI,EAGlB,IAAMD,EAAc,KAAK,OAAOC,CAAK,EAErC,GAAID,IAAgB,KAAM,CACxB,IAAMM,EAAaN,EAAa,KAC1BO,EAAYP,EAAa,KAE/B,OAAAM,EAAY,KAAOC,EACnBA,EAAW,KAAOD,EAElB,KAAK,UACEN,EAAY,GACrB,CAGF,CAQA,SAA+B,CAC7B,IAAIE,EAAc,KAAK,MAGvB,IAFA,CAAC,KAAK,MAAO,KAAK,KAAK,EAAI,CAAC,KAAK,MAAO,KAAK,KAAK,EAE3CA,GAAa,CAClB,IAAMM,EAAON,EAAY,KACzB,CAACA,EAAY,KAAMA,EAAY,IAAI,EAAI,CAACA,EAAY,KAAMA,EAAY,IAAI,EAC1EA,EAAcM,CAChB,CAEA,OAAO,IACT,CAQA,SAAe,CACb,IAAMC,EAAW,CAAC,EACdP,EAAc,KAAK,MAEvB,KAAOA,GACLO,EAAI,KAAKP,EAAY,GAAG,EACxBA,EAAcA,EAAY,KAG5B,OAAOO,CACT,CACF,ECrTA,IAAqBC,EAArB,KAA8B,CAC5B,KAMA,aAAc,CACZ,KAAK,KAAO,IAAIC,CAClB,CAQA,IAAI,OAAuB,CACzB,OAAO,KAAK,KAAK,MAAM,GACzB,CAQA,IAAI,MAAsB,CACxB,OAAO,KAAK,KAAK,MAAM,GACzB,CAQA,IAAI,MAAe,CACjB,OAAO,KAAK,KAAK,IACnB,CAQA,IAAI,SAAmB,CACrB,OAAO,KAAK,KAAK,OACnB,CASA,QAAQC,EAAgB,CACtB,YAAK,KAAK,KAAKA,CAAG,EACX,KAAK,IACd,CAQA,SAAyB,CACvB,OAAO,KAAK,KAAK,MAAM,CACzB,CAQA,MAAsB,CACpB,OAAO,KAAK,KAAK,MAAM,GACzB,CAQA,UAA0B,CACxB,OAAO,KAAK,KAAK,MAAM,GACzB,CAOA,OAAc,CACZ,KAAK,KAAK,MAAM,CAClB,CAQA,SAAe,CACb,OAAO,KAAK,KAAK,QAAQ,CAC3B,CACF,EC/GA,IAAqBC,EAArB,KAA8B,CACpB,KAMR,aAAc,CACZ,KAAK,KAAO,IAAIC,CAClB,CAQA,IAAI,KAAsB,CACxB,OAAO,KAAK,KAAK,MAAM,GACzB,CAQA,IAAI,MAAe,CACjB,OAAO,KAAK,KAAK,IACnB,CAQA,IAAI,SAAmB,CACrB,OAAO,KAAK,OAAS,CACvB,CAQA,KAAKC,EAAc,CACjB,KAAK,KAAK,QAAQA,CAAG,CACvB,CAQA,KAAqB,CACnB,OAAO,KAAK,KAAK,MAAM,CACzB,CAQA,MAAsB,CACpB,OAAO,KAAK,KAAK,MAAM,GACzB,CAMA,OAAc,CACZ,KAAK,KAAK,MAAM,CAClB,CAQA,SAAe,CACb,OAAO,KAAK,KAAK,QAAQ,EAAE,QAAQ,CACrC,CACF,ECzFO,IAAMC,EAAN,MAAMC,CAAW,CAWtB,OAAO,gBAAgBC,EAAuB,CAC5C,GAAIA,GAAS,GAAK,CAAC,OAAO,UAAUA,CAAK,EACvC,MAAM,IAAI,MAAM,qDAAqD,EAEvE,OAAO,KAAK,IAAI,EAAGA,CAAK,EAAI,CAC9B,CAYA,OAAO,oBAAoBC,EAAsB,CAC/C,GAAIA,GAAQ,GAAK,CAAC,OAAO,UAAUA,CAAI,EACrC,MAAM,IAAI,MAAM,oDAAoD,EAEtE,OAAO,KAAK,MAAM,KAAK,KAAKA,EAAO,CAAC,CAAC,CACvC,CAYA,OAAO,qBAAqBC,EAAwB,CAClD,GAAIA,GAAU,GAAK,CAAC,OAAO,UAAUA,CAAM,EACzC,MAAM,IAAI,MAAM,qDAAqD,EAEvE,OAAO,KAAK,MAAM,KAAK,KAAKA,CAAM,CAAC,EAAI,CACzC,CAcA,OAAO,SAA2BC,EAAmC,CACnE,GAAIA,IAAS,KACX,MAAO,GAET,IAAMC,EAAYL,EAAW,SAASI,EAAK,IAAI,EACzCE,EAAaN,EAAW,SAASI,EAAK,KAAK,EACjD,OAAO,KAAK,IAAIC,EAAWC,CAAU,EAAI,CAC3C,CAcA,OAAO,SAA2BF,EAAmC,CACnE,OAAIA,IAAS,KACJ,EAEF,EAAIJ,EAAW,SAAeI,EAAK,IAAI,EAAIJ,EAAW,SAASI,EAAK,KAAK,CAClF,CACF,ECzFO,IAAMG,EAAN,MAAMC,CAAc,CAYzB,OAAO,QAA0BC,EAA2BC,EAA0C,CACpG,OAAID,IAAS,MAAQC,IAAe,KAC3B,GAELD,IAAS,MAAQC,IAAe,MAGhCD,EAAK,MAAQC,EAAW,IACnB,GAEFF,EAAc,QAAcC,EAAK,KAAMC,EAAW,IAAI,GAC3DF,EAAc,QAAcC,EAAK,MAAOC,EAAW,KAAK,CAC5D,CAiBA,OAAO,UAA4BD,EAA6B,CAC9D,IAAME,EAAQC,EAAW,SAAeH,CAAI,EAC5C,OAAOD,EAAc,mBAAmBC,EAAME,EAAO,CAAC,CACxD,CAaA,OAAO,OAAyBF,EAAoC,CAClE,OAAKA,EAIAA,EAAK,OAAS,MAAQA,EAAK,QAAU,MAAUA,EAAK,OAAS,MAAQA,EAAK,QAAU,KAChF,GAEFD,EAAc,OAAOC,EAAK,IAAI,GAAKD,EAAc,OAAOC,EAAK,KAAK,EANhE,EAOX,CAcA,OAAO,WAA6BA,EAAoC,CACtE,GAAI,CAACA,EACH,MAAO,GAET,IAAMI,EAAQ,IAAIC,EAClBD,EAAM,QAAQJ,CAAI,EAClB,IAAIM,EAAkB,GACtB,KAAOF,EAAM,KAAO,GAAG,CACrB,IAAMG,EAAcH,EAAM,QAAQ,EAClC,GAAI,CAACG,EACHD,EAAkB,OACb,CACL,GAAIA,EAEF,MAAO,GAETF,EAAM,QAAQG,EAAY,IAAI,EAC9BH,EAAM,QAAQG,EAAY,KAAK,CACjC,CACF,CACA,MAAO,EACT,CAeA,OAAO,WAA6BP,EAAoC,CACtE,GAAI,CAACA,EACH,MAAO,GAET,IAAMQ,EAAaL,EAAW,SAAeH,EAAK,IAAI,EAChDS,EAAcN,EAAW,SAAeH,EAAK,KAAK,EAExD,OAAI,KAAK,IAAIQ,EAAaC,CAAW,GAAK,EACjCV,EAAc,WAAWC,EAAK,IAAI,GAAKD,EAAc,WAAWC,EAAK,KAAK,EAG5E,EACT,CAWA,OAAe,mBAAqCA,EAA2BE,EAAeQ,EAA+B,CAC3H,OAAIV,IAAS,KACJ,GAELA,EAAK,OAAS,MAAQA,EAAK,QAAU,KAChCE,IAAUQ,EAAe,EAE9BV,EAAK,OAAS,MAAQA,EAAK,QAAU,KAChC,GAGPD,EAAc,mBAAmBC,EAAK,KAAME,EAAOQ,EAAe,CAAC,GACnEX,EAAc,mBAAmBC,EAAK,MAAOE,EAAOQ,EAAe,CAAC,CAExE,CACF,EClKO,IAAKC,OACVA,IAAA,uBACAA,IAAA,qBACAA,IAAA,yBACAA,IAAA,2BAJUA,OAAA,ICQL,IAAMC,EAAN,MAAMC,CAAgB,CAI3B,OAAe,YAAc,CAC1B,EAA0BA,EAAgB,iBAC1C,EAAyBA,EAAgB,gBACzC,EAA2BA,EAAgB,kBAC3C,EAA4BA,EAAgB,kBAC/C,EAkBA,OAAO,YACLC,EACAC,IACqC,CACrC,OAAOF,EAAgB,YAAYE,CAAK,EAAED,CAAI,CAChD,CAmBA,OAAO,QAA0BA,EAA2BE,EAAgCD,EAA8B,CAExH,QAAW,KAAKF,EAAgB,YAAYC,EAAMC,CAAK,EACrDC,EAAY,EAAE,IAAK,EAAE,IAAK,CAAC,CAE/B,CAiBA,OAAO,SAA2BF,EAA2BG,EAAwBF,EAA6C,CAEhI,QAAW,KAAKF,EAAgB,YAAYC,EAAMC,CAAK,EACrD,GAAIE,EAAQ,EAAE,IAAK,EAAE,IAAK,CAAC,EACzB,OAAO,EAGX,OAAO,IACT,CAiBA,OAAO,UAA4BH,EAA2BG,EAAwBF,EAAwC,CAE5H,QAAW,KAAKF,EAAgB,YAAYC,EAAMC,CAAK,EACrD,GAAIE,EAAQ,EAAE,IAAK,EAAE,IAAK,CAAC,EACzB,OAAO,EAAE,GAIf,CAiBA,OAAO,KAAuBH,EAA2BG,EAAwBF,EAAiC,CAEhH,QAAW,KAAKF,EAAgB,YAAYC,EAAMC,CAAK,EACrD,GAAIE,EAAQ,EAAE,IAAK,EAAE,IAAK,CAAC,EACzB,MAAO,GAGX,MAAO,EACT,CAiBA,OAAO,MAAwBH,EAA2BG,EAAwBF,EAAiC,CAEjH,QAAW,KAAKF,EAAgB,YAAYC,EAAMC,CAAK,EACrD,GAAI,CAACE,EAAQ,EAAE,IAAK,EAAE,IAAK,CAAC,EAC1B,MAAO,GAGX,MAAO,EACT,CAYA,OAAgB,mBAAqCH,EAAgE,CACnH,IAAMI,EAA6B,IAAIC,EAIvC,IAHIL,IAAS,MACXI,EAAM,QAAQJ,CAAI,EAEbI,EAAM,MAAM,CACjB,IAAME,EAAcF,EAAM,QAAQ,EAClC,MAAME,EACFA,EAAY,OAAS,MACvBF,EAAM,QAAQE,EAAY,IAAI,EAE5BA,EAAY,QAAU,MACxBF,EAAM,QAAQE,EAAY,KAAK,CAEnC,CACF,CAYA,OAAgB,iBAAmCN,EAAgE,CAC7GA,IAAS,OACX,MAAMA,EAEN,MAAOD,EAAgB,iBAAiBC,EAAK,IAAI,EAEjD,MAAOD,EAAgB,iBAAiBC,EAAK,KAAK,EAEtD,CAYA,OAAgB,gBAAkCA,EAAgE,CAC5GA,IAAS,OAEX,MAAOD,EAAgB,gBAAgBC,EAAK,IAAI,EAChD,MAAMA,EAEN,MAAOD,EAAgB,gBAAgBC,EAAK,KAAK,EAErD,CAYA,OAAgB,kBAAoCA,EAAgE,CAC9GA,IAAS,OAEX,MAAOD,EAAgB,kBAAkBC,EAAK,IAAI,EAElD,MAAOD,EAAgB,kBAAkBC,EAAK,KAAK,EACnD,MAAMA,EAEV,CACF,EC/OO,IAAeO,EAAf,KAA+D,CAC1D,MACA,MAEA,aAAc,CACtB,KAAK,MAAQ,KACb,KAAK,MAAQ,CACf,CAMA,IAAI,MAA4B,CAC9B,OAAO,KAAK,KACd,CAMA,IAAI,MAAe,CACjB,OAAO,KAAK,KACd,CAMA,IAAI,SAAmB,CACrB,OAAO,KAAK,QAAU,CACxB,CAmBA,QAAQC,EAAgCC,EAA8B,CACpEC,EAAgB,QAAc,KAAK,KAAMF,EAAaC,CAAK,CAC7D,CAaA,SAASE,EAAwBF,EAA6C,CAC5E,OAAOC,EAAgB,SAAe,KAAK,KAAMC,EAASF,CAAK,CACjE,CAaA,UAAUE,EAAwBF,EAAuC,CACvE,OAAOC,EAAgB,UAAU,KAAK,KAAMC,EAASF,CAAK,CAC5D,CAaA,KAAKE,EAAwBF,EAAiC,CAC5D,OAAOC,EAAgB,KAAW,KAAK,KAAMC,EAASF,CAAK,CAC7D,CAaA,MAAME,EAAwBF,EAAiC,CAC7D,OAAOC,EAAgB,MAAY,KAAK,KAAMC,EAASF,CAAK,CAC9D,CASA,OAAc,CACZ,KAAK,QAAQ,IAAI,EACjB,KAAK,QAAQ,CAAC,CAChB,CASA,UAAmB,CACjB,OAAOG,EAAW,SAAS,KAAK,IAAI,CACtC,CAUA,QAAQC,EAAoC,CAC1C,OAAOC,EAAc,QAAc,KAAK,KAAMD,CAAI,CACpD,CAUA,WAAqB,CACnB,OAAOC,EAAc,UAAU,KAAK,IAAI,CAC1C,CAUA,QAAkB,CAChB,OAAOA,EAAc,OAAa,KAAK,IAAI,CAC7C,CAWA,YAAsB,CACpB,OAAOA,EAAc,WAAiB,KAAK,IAAI,CACjD,CAWA,YAAsB,CACpB,OAAOA,EAAc,WAAiB,KAAK,IAAI,CACjD,CAYA,CAAC,KAAKL,EAAkD,CAEtD,QAAWM,KAAQL,EAAgB,YAAkB,KAAK,KAAMD,CAAK,EACnE,MAAMM,EAAK,GAEf,CAYA,CAAC,OAAON,EAAkD,CAExD,QAAWM,KAAQL,EAAgB,YAAkB,KAAK,KAAMD,CAAK,EACnE,MAAMM,EAAK,GAEf,CAYA,CAAC,QAAQN,EAAuD,CAE9D,QAAWM,KAAQL,EAAgB,YAAkB,KAAK,KAAMD,CAAK,EACnE,KAAM,CAACM,EAAK,IAAKA,EAAK,GAAG,CAE7B,CAYA,CAAC,MAAMN,EAA6D,CAElE,QAAWM,KAAQL,EAAgB,YAAkB,KAAK,KAAMD,CAAK,EACnE,MAAMM,CAEV,CACU,QAAQF,EAAiC,CACjD,KAAK,MAAQA,CACf,CACU,QAAQG,EAAsB,CACtC,KAAK,MAAQA,CACf,CACF,ECtRO,IAAMC,EAAN,KAA+B,CACpC,IACA,IACA,KACA,MAMA,YAAYC,EAAQC,EAAQ,CAC1B,KAAK,IAAMD,EACX,KAAK,IAAMC,EACX,KAAK,KAAO,KACZ,KAAK,MAAQ,IACf,CACF,ECbO,IAAMC,EAAN,KAAuB,CAiB5B,OAAO,IAAsBC,EAAoBC,EAAQC,EAAiC,CACxF,IAAMC,EAAU,IAAIC,EAAOH,EAAKC,CAAG,EAEnC,GAAIF,IAAS,KACX,MAAO,CAACG,EAAS,EAAI,EAGvB,QAAWE,KAAKC,EAAgB,YAAkBN,GAA+B,EAAG,CAClF,GAAIK,EAAE,OAAS,KACb,OAAAA,EAAE,KAAOF,EACF,CAACH,EAAM,EAAI,EAEpB,GAAIK,EAAE,QAAU,KACd,OAAAA,EAAE,MAAQF,EACH,CAACH,EAAM,EAAI,CAEtB,CACF,CAkBA,OAAO,QAA0BA,EAAoBO,EAAgD,CACnG,IAAIC,EAAgB,EAEpB,GAAID,EAAQ,SAAW,EACrB,MAAO,CAACP,EAAMQ,CAAK,EAGrB,IAAMC,EAA6B,IAAIC,EACnCC,EAAQ,EAUZ,IARIX,IAAS,OACXA,EAAO,IAAII,EAAO,GAAGG,EAAQI,CAAK,CAAC,EACnCA,IACAH,KAGFC,EAAM,QAAQT,CAAI,EAEXW,EAAQJ,EAAQ,QAAUE,EAAM,KAAO,GAAG,CAC/C,IAAMG,EAAcH,EAAM,QAAQ,EAE9BG,EAAY,OAAS,OACvBA,EAAY,KAAO,IAAIR,EAAO,GAAGG,EAAQI,CAAK,CAAC,EAC/CA,IACAH,KAGFC,EAAM,QAAQG,EAAY,IAAI,EAE1BD,EAAQJ,EAAQ,QAAUK,EAAY,QAAU,OAClDA,EAAY,MAAQ,IAAIR,EAAO,GAAGG,EAAQI,CAAK,CAAC,EAChDA,IACAH,KAGFC,EAAM,QAAQG,EAAY,KAAK,CACjC,CAEA,MAAO,CAACZ,EAAMQ,CAAK,CACrB,CAmBA,OAAO,IAAsBR,EAAoBC,EAAQC,EAAQW,EAAiC,CAChG,IAAMC,EAAOR,EAAgB,SAAeN,EAAM,CAACe,EAAIC,IAAMA,IAAMf,EAAKY,CAAK,EAC7E,OAAIC,IAAS,MACXA,EAAK,IAAMZ,EACJ,IAEF,EACT,CAeA,OAAO,OAAyBF,EAAoBC,EAAwC,CAC1F,GAAID,IAAS,KACX,MAAO,CAAC,KAAM,EAAK,EAGrB,GAAIA,EAAK,OAAS,MAAQA,EAAK,QAAU,MAAQA,EAAK,MAAQC,EAC5D,MAAO,CAAC,KAAM,EAAI,EAGpB,IAAIgB,EAA+B,KAC/BC,EAAkD,KAClDC,EAA4C,KAIhD,QAAWd,KAAKC,EAAgB,YAAkBN,GAA+B,EAC3EK,EAAE,MAAQJ,IACZgB,EAAUZ,IAERA,EAAE,OAAS,MAAQA,EAAE,QAAU,QACjCa,EAA6Bb,GAE/Bc,EAAuBd,EAIzB,OAAKY,GAKDE,IAAyBF,IAC3BA,EAAQ,IAAME,EAAqB,IACnCF,EAAQ,IAAME,EAAqB,KAIjCD,EAA2B,OAASC,EACtCD,EAA2B,KAAO,KACzBA,EAA2B,QAAUC,IAC9CD,EAA2B,MAAQ,MAG9B,CAAClB,EAAM,EAAI,GAhBT,CAACA,EAAM,EAAK,CAiBvB,CACF,EC7KA,IAAqBoB,EAArB,MAAqBC,UAAoDC,CAAoB,CAQ3F,YAAYC,EAA4BC,EAAe,CACrD,MAAM,EACFD,IACF,KAAK,QAAQA,CAAI,EACjB,KAAK,QAAQC,GAAQC,EAAW,SAAeF,CAAI,CAAC,EAExD,CAYA,OAAO,YAA8BG,EAA0C,CAC7E,GAAM,CAACH,EAAMI,CAAK,EAAIC,EAAiB,QAAc,KAAMF,CAAO,EAClE,OAAO,IAAIL,EAAWE,EAAMI,CAAK,CACnC,CAaA,IAAIE,EAAQC,EAAuC,CACjD,OAAO,KAAK,UAAU,CAACC,EAAIC,IAAMA,IAAMH,EAAKC,CAAK,CACnD,CAaA,KAAKD,EAAQC,EAAsC,CACjD,OAAO,KAAK,SAAS,CAACC,EAAIC,IAAMA,IAAMH,EAAKC,CAAK,CAClD,CAaA,IAAID,EAAQC,EAAiC,CAC3C,OAAO,KAAK,KAAK,CAACC,EAAIC,IAAMA,IAAMH,EAAKC,CAAK,CAC9C,CAcA,IAAID,EAAQI,EAAQH,EAAiC,CACnD,OAAOF,EAAiB,IAAU,KAAK,KAAMC,EAAKI,EAAKH,CAAK,CAC9D,CAWA,IAAID,EAAQI,EAAc,CACxB,GAAM,CAACV,EAAMW,CAAS,EAAIN,EAAiB,IAAU,KAAK,KAAMC,EAAKI,CAAG,EACpEC,IACF,KAAK,QAAQX,CAAI,EACjB,KAAK,QAAQ,KAAK,KAAO,CAAC,EAE9B,CAUA,QAAQG,EAA8B,CACpC,GAAM,CAACH,EAAMI,CAAK,EAAIC,EAAiB,QAAc,KAAK,KAAMF,CAAO,EACnEC,EAAQ,IACV,KAAK,QAAQJ,CAAI,EACjB,KAAK,QAAQ,KAAK,KAAOI,CAAK,EAElC,CAWA,OAAOE,EAAiB,CACtB,GAAM,CAACN,EAAMW,CAAS,EAAIN,EAAiB,OAAa,KAAK,KAAMC,CAAG,EACtE,OAAIK,IACF,KAAK,QAAQX,CAAI,EACjB,KAAK,QAAQ,KAAK,KAAO,CAAC,GAErBW,CACT,CACF,ECzJO,IAAMC,EAAwC,CAACC,EAAGC,IAAMD,EAAIC,EACtDC,EAAoC,CAACF,EAAGC,IAAMD,EAAE,cAAcC,EAAG,OAAW,CAAE,YAAa,MAAO,CAAC,EAKnGE,EAAN,MAAMC,CAAU,CAarB,OAAO,IAAsBC,EAAoBC,EAAQC,EAA6C,CACpG,OAAOH,EAAU,KAAWC,EAAMC,EAAKC,CAAU,GAAG,GACtD,CAcA,OAAO,KAAuBF,EAAoBC,EAAQC,EAAmD,CAC3G,GAAIF,IAAS,KACX,OAAO,KAGT,IAAMG,EAAgBD,EAAWD,EAAKD,EAAK,GAAG,EAE9C,OAAIG,IAAkB,EACbH,EAELG,EAAgB,EACXJ,EAAU,KAAKC,EAAK,KAAMC,EAAKC,CAAU,EAE3CH,EAAU,KAAKC,EAAK,MAAOC,EAAKC,CAAU,CACnD,CAcA,OAAO,IAAsBF,EAAoBC,EAAQC,EAAuC,CAC9F,MAAO,CAAC,CAACH,EAAU,KAAWC,EAAMC,EAAKC,CAAU,CACrD,CAcA,OAAO,kBAAoCE,EAAwBC,EAAeC,EAAmC,CACnH,GAAID,EAAQC,EACV,OAAO,KAGT,IAAMC,EAAM,KAAK,OAAOF,EAAQC,GAAO,CAAC,EAClCE,EAAO,IAAIC,EAAa,GAAGL,EAAQG,CAAG,CAAC,EAE7C,OAAAC,EAAK,KAAOT,EAAU,kBAAwBK,EAASC,EAAOE,EAAM,CAAC,EACrEC,EAAK,MAAQT,EAAU,kBAAwBK,EAASG,EAAM,EAAGD,CAAG,EAC7DE,CACT,CAeA,OAAO,IAAsBR,EAAoBC,EAAQS,EAAQR,EAAuC,CACtG,IAAMM,EAAOT,EAAU,KAAWC,EAAMC,EAAKC,CAAU,EACvD,OAAIM,IAAS,MACXA,EAAK,IAAME,EACJ,IAEF,EACT,CAcA,OAAO,IAAsBV,EAAoBC,EAAQS,EAAQR,EAAuD,CACtH,GAAIF,IAAS,KACX,MAAO,CAAC,IAAIS,EAAaR,EAAKS,CAAG,EAAG,EAAI,EAG1C,IAAMP,EAAgBD,EAAWD,EAAKD,EAAK,GAAG,EAE9C,GAAIG,EAAgB,EAAG,CACrB,GAAM,CAACK,EAAMG,CAAS,EAAIZ,EAAU,IAAIC,EAAK,KAAMC,EAAKS,EAAKR,CAAU,EACvE,OAAAF,EAAK,KAAOQ,EACL,CAACR,EAAMW,CAAS,CACzB,SAAWR,EAAgB,EAAG,CAC5B,GAAM,CAACK,EAAMG,CAAS,EAAIZ,EAAU,IAAIC,EAAK,MAAOC,EAAKS,EAAKR,CAAU,EACxE,OAAAF,EAAK,MAAQQ,EACN,CAACR,EAAMW,CAAS,CACzB,KACE,gBAAQ,KAAK,6BAA6B,EACnC,CAACX,EAAM,EAAK,CAEvB,CAeA,OAAO,OAAyBA,EAA2BC,EAAQC,EAA8BU,EAAmB,GAAuC,CACzJ,GAAIZ,IAAS,KACX,MAAO,CAAC,KAAMY,CAAO,EAGvB,IAAMC,EAAmBX,EAAWD,EAAKD,EAAK,GAAG,EAEjD,GAAIa,EAAmB,EAAG,CACxB,GAAM,CAACC,EAAKC,CAAU,EAAIhB,EAAU,OAAOC,EAAK,KAAMC,EAAKC,EAAYU,CAAO,EAC9EA,EAAUG,EACVf,EAAK,KAAOc,CACd,SAAWD,EAAmB,EAAG,CAC/B,GAAM,CAACG,EAAOD,CAAS,EAAIhB,EAAU,OAAOC,EAAK,MAAOC,EAAKC,EAAYU,CAAO,EAChFA,EAAUG,EACVf,EAAK,MAAQgB,CACf,KAAO,CAKL,GAHAJ,EAAU,GAGNZ,EAAK,OAAS,KAChB,MAAO,CAACA,EAAK,MAAOY,CAAO,EACtB,GAAIZ,EAAK,QAAU,KACxB,MAAO,CAACA,EAAK,KAAMY,CAAO,EAI5B,IAAMK,EAAYlB,EAAU,SAASC,EAAK,KAAK,EAE/CA,EAAK,IAAMiB,EAAU,IACrBjB,EAAK,IAAMiB,EAAU,IAErB,GAAM,CAACD,CAAK,EAAIjB,EAAU,OAAOC,EAAK,MAAOA,EAAK,IAAKE,EAAYU,CAAO,EAC1EZ,EAAK,MAAQgB,CACf,CAEA,MAAO,CAAChB,EAAMY,CAAO,CACvB,CAWA,OAAe,SAA2BZ,EAAgD,CACxF,IAAIkB,EAAclB,EAElB,KAAOkB,GAAeA,GAAa,OAAS,MAC1CA,EAAcA,EAAY,KAE5B,OAAOA,CACT,CACF,EChNA,IAAqBC,EAArB,MAAqBC,UAA0DC,CAAoB,CAChF,WAWjB,YAAYC,EAA+BC,EAAwBC,EAAe,CAChF,MAAM,EACN,KAAK,WAAaF,GAAcG,EAC5BF,IACF,KAAK,QAAQA,CAAO,EACpB,KAAK,QAAQC,GAAQE,EAAW,SAAeH,CAAO,CAAC,EAE3D,CAaA,OAAO,YAA6CI,EAAwBL,EAAuD,CACjI,IAAMM,EAAK,IAAIR,EAAuBE,CAAU,EAChD,OAAAM,EAAI,QAAQD,CAAO,EACZC,CACT,CAaA,OAAO,kBAAoCD,EAAwBL,EAAuD,CACxH,IAAMC,EAAUM,EAAU,kBAAwBF,EAAS,EAAGA,EAAQ,OAAS,CAAC,EAC1EH,EAAOG,EAAQ,OACrB,GAAIJ,EACF,OAAO,IAAIH,EAAuBE,EAAYC,EAASC,CAAI,CAE/D,CASA,IAAIM,EAAuB,CACzB,OAAOD,EAAU,IAAU,KAAK,KAAMC,EAAK,KAAK,UAAU,CAC5D,CASA,KAAKA,EAA6B,CAChC,OAAOD,EAAU,KAAW,KAAK,KAAMC,EAAK,KAAK,UAAU,CAC7D,CASA,IAAIA,EAAiB,CACnB,OAAOD,EAAU,IAAU,KAAK,KAAMC,EAAK,KAAK,UAAU,CAC5D,CAUA,IAAIA,EAAQC,EAAiB,CAC3B,GAAM,CAACC,EAAMC,CAAS,EAAIJ,EAAU,IAAU,KAAK,KAAMC,EAAKC,EAAK,KAAK,UAAU,EAClF,OAAIE,IACF,KAAK,QAAQD,CAAI,EACjB,KAAK,QAAQ,KAAK,KAAO,CAAC,GAErBC,CACT,CASA,QAAQN,EAAgC,CACtC,IAAIO,EAAgB,EACpB,OAAS,CAACJ,EAAKC,CAAG,IAAKJ,EACrBO,EAAQ,KAAK,IAAIJ,EAAKC,CAAG,EAAIG,EAAQ,EAAIA,EAE3C,OAAOA,CACT,CAUA,IAAIJ,EAAQC,EAAiB,CAC3B,OAAOF,EAAU,IAAI,KAAK,KAAMC,EAAKC,EAAK,KAAK,UAAU,CAC3D,CASA,OAAOD,EAAiB,CACtB,GAAM,CAACE,EAAMG,CAAS,EAAIN,EAAU,OAAa,KAAK,KAAMC,EAAK,KAAK,UAAU,EAChF,OAAIK,IACF,KAAK,QAAQH,CAAI,EACjB,KAAK,QAAQ,KAAK,KAAO,CAAC,GAErBG,CACT,CACF","names":["src_exports","__export","BTNode","BinarySearchTree","BinaryTree","DoublyLinkedList","Queue","SinglyLinkedList","Stack","TraversalOrder","numericCompare","strCompare","__toCommonJS","LLNode","BaseLinkedList","index","SLLNode","LLNode","val","SinglyLinkedList","_SinglyLinkedList","BaseLinkedList","data","list","item","newNode","currentNode","removedNode","index","i","beforeNode","afterNode","nextNode","prevNode","n","rotation","arr","DLLNode","LLNode","val","DoublyLinkedList","_DoublyLinkedList","BaseLinkedList","data","list","item","newNode","removedNode","index","currentNode","count","direction","i","beforeNode","afterNode","next","arr","Queue","SinglyLinkedList","val","Stack","SinglyLinkedList","val","CalcHelper","_CalcHelper","depth","size","leaves","root","leftDepth","rightDepth","CompareHelper","_CompareHelper","root","targetRoot","depth","CalcHelper","queue","Queue","encounteredNull","currentNode","leftHeight","rightHeight","currentLevel","TraversalOrder","TraversalHelper","_TraversalHelper","root","order","traversalFn","matchFn","queue","Queue","currentNode","BinaryTreeBase","traversalFn","order","TraversalHelper","matchFn","CalcHelper","root","CompareHelper","node","number","BTNode","key","val","BTMutationHelper","root","key","val","newNode","BTNode","n","TraversalHelper","entries","count","queue","Queue","index","currentNode","order","node","_v","k","keyNode","parentDeepestRightMostNode","deepestRightMostNode","BinaryTree","_BinaryTree","BinaryTreeBase","root","size","CalcHelper","entries","count","BTMutationHelper","key","order","_v","k","val","isSuccess","numericCompare","a","b","strCompare","BSTHelper","_BSTHelper","root","key","comparator","compareResult","entries","start","end","mid","node","BTNode","val","isSuccess","deleted","comparisonResult","left","isDeleted","right","successor","currentNode","BinarySearchTree","_BinarySearchTree","BinaryTreeBase","comparator","bstRoot","size","numericCompare","CalcHelper","entries","bst","BSTHelper","key","val","root","isSuccess","count","isDeleted"]}