All files / data_structures / _binary_search_node.ts

100.00% Branches 15/15
100.00% Lines 49/49
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
 
 
 
 
x94
x94
x2043
x2043
x94
 
x94
x2043
x2043
x2043
x2043
x2043
 
x94
x120
x120
x120
 
x120
x120
x120
x120
 
x94
x901
x901
x901
x901
x901
x901
x901
x901
 
x94
x499
x499
x499
x499
 
x94
x260
x260
x260
x260
 
x94
x182
x270
x270
x182
x184
x184
x184
x184
x182
x94



























































// Copyright 2018-2025 the Deno authors. MIT license.
// This module is browser compatible.

export type Direction = "left" | "right";

export class BinarySearchNode<T> {
  left: BinarySearchNode<T> | null;
  right: BinarySearchNode<T> | null;
  parent: BinarySearchNode<T> | null;
  value: T;

  constructor(parent: BinarySearchNode<T> | null, value: T) {
    this.left = null;
    this.right = null;
    this.parent = parent;
    this.value = value;
  }

  static from<T>(node: BinarySearchNode<T>): BinarySearchNode<T> {
    const copy: BinarySearchNode<T> = new BinarySearchNode(
      node.parent,
      node.value,
    );
    copy.left = node.left;
    copy.right = node.right;
    return copy;
  }

  directionFromParent(): Direction | null {
    return this.parent === null
      ? null
      : this === this.parent.left
      ? "left"
      : this === this.parent.right
      ? "right"
      : null;
  }

  findMinNode(): BinarySearchNode<T> {
    let minNode: BinarySearchNode<T> | null = this.left;
    while (minNode?.left) minNode = minNode.left;
    return minNode ?? this;
  }

  findMaxNode(): BinarySearchNode<T> {
    let maxNode: BinarySearchNode<T> | null = this.right;
    while (maxNode?.right) maxNode = maxNode.right;
    return maxNode ?? this;
  }

  findSuccessorNode(): BinarySearchNode<T> | null {
    if (this.right !== null) return this.right.findMinNode();
    let parent: BinarySearchNode<T> | null = this.parent;
    let direction: Direction | null = this.directionFromParent();
    while (parent && direction === "right") {
      direction = parent.directionFromParent();
      parent = parent.parent;
    }
    return parent;
  }
}