Options
All
  • Public
  • Public/Protected
  • All
Menu

Class BST<T>

Type parameters

  • T

Hierarchy

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Properties

Protected $ROOT

$ROOT: null | Node<T>

Protected compare

compare: compare<T>

Accessors

height

  • get height(): number

toArray

  • get toArray(): T[]

Methods

Protected adjustHeight

  • adjustHeight(node: null | Node<T>): void

  • Parameters

    • node: null | Node<T>

    Returns void

delete

  • delete(data: T): void

  • Parameters

    • data: T

    Returns void

deleteElement

  • deleteElement(target: Node<T>): void

  • Parameters

    • target: Node<T>

    Returns void

findNode

  • findNode(data: T, end?: boolean, root?: null | Node<T>): null | Node<T>

  • Find Node with data in BST

    It find the node with the given data and if node doesn't exists it return null

    Parameters

    • data: T

      target data to search

    • end: boolean = false

      Get first occurrence of node

    • root: null | Node<T> = ...

    Returns null | Node<T>

    Node in BST | Null if node not found

Private inorder

  • inorder(root: null | Node<T>, array?: T[]): T[]

  • Parameters

    • root: null | Node<T>
    • array: T[] = []

    Returns T[]

insert

  • insert(data: T): Node<T>

  • Parameters

    • data: T

    Returns Node<T>

Protected insertionPoint

  • insertionPoint(data: T, root?: null | Node<T>): null | Node<T>

  • Find Insertion Point for new Node in BST

    It find the node with the given data and if node doesn't exists it return the position where the node can be inserted.

    Parameters

    • data: T

      target data to insert

    • root: null | Node<T> = ...

    Returns null | Node<T>

    Node in BST | Null if tree is empty

Private leftAncestor

  • leftAncestor(node: Node<T>): null | Node<T>

  • Get Left Ancestor of a Node

    Parameters

    • node: Node<T>

      The reference node

    Returns null | Node<T>

    The ancestor of a node with the next largest data | null if right ancestor doesn't exists

Private leftDescendant

  • leftDescendant(node: Node<T>): Node<T>

  • Parameters

    • node: Node<T>

    Returns Node<T>

next

  • next(node: Node<T>): null | Node<T>

  • Get Next Node in BST

    Parameters

    • node: Node<T>

      The reference node

    Returns null | Node<T>

    Inorder Successor | null if current node is largest

prev

  • prev(node: Node<T>): null | Node<T>

rangeSearch

  • rangeSearch(start: T, end: T): Node<T>[]

  • Search List of Nodes

    Parameters

    • start: T

      staring value for search

    • end: T

      ending value for search

    Returns Node<T>[]

    A list of nodes within range [start, end]

Private rightAncestor

  • rightAncestor(node: Node<T>): null | Node<T>

  • Get Right Ancestor of a Node

    Parameters

    • node: Node<T>

      The reference node

    Returns null | Node<T>

    The ancestor of a node with the next largest data | null if right ancestor doesn't exists

Private rightDescendant

  • rightDescendant(node: Node<T>): Node<T>

  • Parameters

    • node: Node<T>

    Returns Node<T>