Tree និង Binary Search Tree

        A          <- root
       / \
      B   C
     / \   \
    D   E   F      <- D, E, F are leaves

class TreeNode<T> {
  children: TreeNode<T>[] = [];

  constructor(public value: T) {}

  add(value: T): TreeNode<T> {
    const child = new TreeNode(value);
    this.children.push(child);
    return child; // so we can keep adding below the new node
  }
}

const root = new TreeNode("src");
const components = root.add("components");
components.add("Button.tsx");
components.add("Navbar.tsx");
root.add("lib").add("api.ts");
root.add("index.ts");

src
├── components
│   ├── Button.tsx
│   └── Navbar.tsx
├── lib
│   └── api.ts
└── index.ts

function preorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  visit(root.value);
  for (const child of root.children) preorder(child, visit);
}

const seen: string[] = [];
preorder(root, (v) => seen.push(v));
console.log(seen.join(", "));
// src, components, Button.tsx, Navbar.tsx, lib, api.ts, index.ts

function postorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  for (const child of root.children) postorder(child, visit);
  visit(root.value);
}

const done: string[] = [];
postorder(root, (v) => done.push(v));
console.log(done.join(", "));
// Button.tsx, Navbar.tsx, components, api.ts, lib, index.ts, src

interface Entry {
  name: string;
  size: number; // for a file; folders use 0
}

const files = new TreeNode<Entry>({ name: "src", size: 0 });
const ui = files.add({ name: "components", size: 0 });
ui.add({ name: "Button.tsx", size: 3 });
ui.add({ name: "Navbar.tsx", size: 5 });
files.add({ name: "index.ts", size: 2 });

function totalSize(node: TreeNode<Entry>): number {
  let total = node.value.size;
  for (const child of node.children) total += totalSize(child);
  return total;
}

console.log(totalSize(files)); // 10
console.log(totalSize(ui));    // 8

function levelOrder<T>(root: TreeNode<T>): T[][] {
  const levels: T[][] = [];
  let current: TreeNode<T>[] = [root];

  while (current.length > 0) {
    levels.push(current.map((n) => n.value));
    current = current.flatMap((n) => n.children);
  }
  return levels;
}

console.log(JSON.stringify(levelOrder(root)));
// [["src"],["components","lib","index.ts"],["Button.tsx","Navbar.tsx","api.ts"]]

          50
        /    \
      30      70
     /  \    /  \
    20  40  60  80

20, 30, 40, 50, 60, 70, 80

class BSTNode<T> {
  left: BSTNode<T> | null = null;
  right: BSTNode<T> | null = null;

  constructor(public value: T) {}
}

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

class BinarySearchTree<T> {
  private root: BSTNode<T> | null = null;
  private count = 0;

  constructor(private compare: (a: T, b: T) => number = defaultCompare) {}

  get size(): number {
    return this.count;
  }
}

has(value: T): boolean {
  let node = this.root;
  while (node !== null) {
    const c = this.compare(value, node.value);
    if (c === 0) return true;
    node = c < 0 ? node.left : node.right;
  }
  return false;
}

insert(value: T): boolean {
  if (this.root === null) {
    this.root = new BSTNode(value);
    this.count++;
    return true;
  }

  let node = this.root;
  while (true) {
    const c = this.compare(value, node.value);
    if (c === 0) return false; // already there: no duplicates
    const side = c < 0 ? "left" : "right";
    const next = node[side];
    if (next === null) {
      node[side] = new BSTNode(value);
      this.count++;
      return true;
    }
    node = next;
  }
}

min(): T | undefined {
  if (this.root === null) return undefined;
  return minNode(this.root).value;
}

max(): T | undefined {
  let node = this.root;
  if (node === null) return undefined;
  while (node.right !== null) node = node.right;
  return node.value;
}

inOrder(): T[] {
  const out: T[] = [];
  const walk = (node: BSTNode<T> | null): void => {
    if (node === null) return;
    walk(node.left);
    out.push(node.value);
    walk(node.right);
  };
  walk(this.root);
  return out;
}

function minNode<T>(node: BSTNode<T>): BSTNode<T> {
  while (node.left !== null) node = node.left;
  return node;
}

Before:        50              After:         50
             /    \                         /    \
           30      70                     40      70
          /  \    /  \                   /       /  \
        20   40  60  80                20       60  80

delete(value: T): boolean {
  const before = this.count;
  this.root = this.deleteFrom(this.root, value);
  return this.count < before;
}

private deleteFrom(node: BSTNode<T> | null, value: T): BSTNode<T> | null {
  if (node === null) return null; // not found: nothing changes

  const c = this.compare(value, node.value);
  if (c < 0) {
    node.left = this.deleteFrom(node.left, value);
    return node;
  }
  if (c > 0) {
    node.right = this.deleteFrom(node.right, value);
    return node;
  }

  // Found it. Cases 1 and 2: zero or one child.
  if (node.left === null) {
    this.count--;
    return node.right;
  }
  if (node.right === null) {
    this.count--;
    return node.left;
  }

  // Case 3: two children. Copy the successor here, then delete it below.
  const successor = minNode(node.right);
  node.value = successor.value;
  node.right = this.deleteFrom(node.right, successor.value);
  return node;
}

height(): number {
  const h = (node: BSTNode<T> | null): number =>
    node === null ? -1 : 1 + Math.max(h(node.left), h(node.right));
  return h(this.root);
}

1
 \
  2
   \
    3
     \
      4  ...and so on down to 7

interface BinaryNode {
  value: number;
  left: BinaryNode | null;
  right: BinaryNode | null;
}

const node = (
  value: number,
  left: BinaryNode | null = null,
  right: BinaryNode | null = null,
): BinaryNode => ({ value, left, right });

function isValidBST(
  root: BinaryNode | null,
  low = -Infinity,
  high = Infinity,
): boolean {
  if (root === null) return true;
  if (root.value <= low || root.value >= high) return false;
  return (
    isValidBST(root.left, low, root.value) &&
    isValidBST(root.right, root.value, high)
  );
}

const good = node(50, node(30, node(20), node(40)), node(70));
const bad = node(50, node(30, node(20), node(60)), node(70));

console.log(isValidBST(good)); // true
console.log(isValidBST(bad));  // false  (60 is in the left subtree of 50)

function invert(root: BinaryNode | null): BinaryNode | null {
  if (root === null) return null;
  const left = invert(root.left);
  const right = invert(root.right);
  root.left = right;
  root.right = left;
  return root;
}

function lowestCommonAncestor(root: BinaryNode, p: number, q: number): number {
  let current = root;
  while (true) {
    if (p < current.value && q < current.value) current = current.left!;
    else if (p > current.value && q > current.value) current = current.right!;
    else return current.value;
  }
}

const tree = node(
  50,
  node(30, node(20), node(40)),
  node(70, node(60), node(80)),
);

console.log(lowestCommonAncestor(tree, 20, 40)); // 30
console.log(lowestCommonAncestor(tree, 20, 60)); // 50
console.log(lowestCommonAncestor(tree, 30, 40)); // 30  (a node can be its own ancestor)

function rightSideView(root: BinaryNode | null): number[] {
  if (root === null) return [];
  const view: number[] = [];
  let level = [root];

  while (level.length > 0) {
    view.push(level[level.length - 1].value);
    level = level.flatMap((n) =>
      [n.left, n.right].filter((c): c is BinaryNode => c !== null),
    );
  }
  return view;
}

console.log(rightSideView(tree)); // [ 50, 70, 80 ]

function inOrderIterative(root: BinaryNode | null): number[] {
  const out: number[] = [];
  const stack: BinaryNode[] = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current); // remember the way back
      current = current.left;
    }
    const top = stack.pop()!;
    out.push(top.value);
    current = top.right;
  }
  return out;
}

// ---------- A general tree (DOM, folders, menus) ----------

export class TreeNode<T> {
  children: TreeNode<T>[] = [];

  constructor(public value: T) {}

  add(value: T): TreeNode<T> {
    const child = new TreeNode(value);
    this.children.push(child);
    return child;
  }
}

export function preorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  visit(root.value);
  for (const child of root.children) preorder(child, visit);
}

export function postorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  for (const child of root.children) postorder(child, visit);
  visit(root.value);
}

export function levelOrder<T>(root: TreeNode<T>): T[][] {
  const levels: T[][] = [];
  let current: TreeNode<T>[] = [root];
  while (current.length > 0) {
    levels.push(current.map((n) => n.value));
    current = current.flatMap((n) => n.children);
  }
  return levels;
}

export function treeHeight<T>(root: TreeNode<T> | null): number {
  if (root === null) return -1;
  let tallest = -1;
  for (const child of root.children) {
    tallest = Math.max(tallest, treeHeight(child));
  }
  return tallest + 1;
}

// ---------- A binary search tree ----------

class BSTNode<T> {
  left: BSTNode<T> | null = null;
  right: BSTNode<T> | null = null;
  constructor(public value: T) {}
}

export class BinarySearchTree<T> {
  private root: BSTNode<T> | null = null;
  private count = 0;

  constructor(private compare: (a: T, b: T) => number = defaultCompare) {}

  get size(): number {
    return this.count;
  }

  insert(value: T): boolean {
    if (this.root === null) {
      this.root = new BSTNode(value);
      this.count++;
      return true;
    }
    let node = this.root;
    while (true) {
      const c = this.compare(value, node.value);
      if (c === 0) return false;
      const side = c < 0 ? "left" : "right";
      const next = node[side];
      if (next === null) {
        node[side] = new BSTNode(value);
        this.count++;
        return true;
      }
      node = next;
    }
  }

  has(value: T): boolean {
    let node = this.root;
    while (node !== null) {
      const c = this.compare(value, node.value);
      if (c === 0) return true;
      node = c < 0 ? node.left : node.right;
    }
    return false;
  }

  min(): T | undefined {
    if (this.root === null) return undefined;
    return minNode(this.root).value;
  }

  max(): T | undefined {
    let node = this.root;
    if (node === null) return undefined;
    while (node.right !== null) node = node.right;
    return node.value;
  }

  delete(value: T): boolean {
    const before = this.count;
    this.root = this.deleteFrom(this.root, value);
    return this.count < before;
  }

  private deleteFrom(node: BSTNode<T> | null, value: T): BSTNode<T> | null {
    if (node === null) return null;
    const c = this.compare(value, node.value);
    if (c < 0) {
      node.left = this.deleteFrom(node.left, value);
      return node;
    }
    if (c > 0) {
      node.right = this.deleteFrom(node.right, value);
      return node;
    }
    if (node.left === null) {
      this.count--;
      return node.right;
    }
    if (node.right === null) {
      this.count--;
      return node.left;
    }
    // Two children: copy the in-order successor here, then delete it below.
    const successor = minNode(node.right);
    node.value = successor.value;
    node.right = this.deleteFrom(node.right, successor.value);
    return node;
  }

  inOrder(): T[] {
    const out: T[] = [];
    const walk = (node: BSTNode<T> | null): void => {
      if (node === null) return;
      walk(node.left);
      out.push(node.value);
      walk(node.right);
    };
    walk(this.root);
    return out;
  }

  levelOrder(): T[][] {
    const levels: T[][] = [];
    let current: BSTNode<T>[] = this.root === null ? [] : [this.root];
    while (current.length > 0) {
      levels.push(current.map((n) => n.value));
      const next: BSTNode<T>[] = [];
      for (const n of current) {
        if (n.left !== null) next.push(n.left);
        if (n.right !== null) next.push(n.right);
      }
      current = next;
    }
    return levels;
  }

  height(): number {
    const h = (node: BSTNode<T> | null): number =>
      node === null ? -1 : 1 + Math.max(h(node.left), h(node.right));
    return h(this.root);
  }
}

function minNode<T>(node: BSTNode<T>): BSTNode<T> {
  while (node.left !== null) node = node.left;
  return node;
}

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  TreeNode,
  preorder,
  postorder,
  levelOrder,
  treeHeight,
  BinarySearchTree,
} from "./bst.ts";

function sample(): TreeNode<string> {
  const root = new TreeNode("src");
  const components = root.add("components");
  components.add("Button.tsx");
  components.add("Navbar.tsx");
  root.add("lib").add("api.ts");
  root.add("index.ts");
  return root;
}

test("preorder visits a parent before its children", () => {
  const seen: string[] = [];
  preorder(sample(), (v) => seen.push(v));
  assert.deepEqual(seen, [
    "src", "components", "Button.tsx", "Navbar.tsx", "lib", "api.ts", "index.ts",
  ]);
});

test("postorder visits children before the parent", () => {
  const seen: string[] = [];
  postorder(sample(), (v) => seen.push(v));
  assert.deepEqual(seen, [
    "Button.tsx", "Navbar.tsx", "components", "api.ts", "lib", "index.ts", "src",
  ]);
});

test("levelOrder groups by depth, and height counts edges", () => {
  assert.deepEqual(levelOrder(sample()), [
    ["src"],
    ["components", "lib", "index.ts"],
    ["Button.tsx", "Navbar.tsx", "api.ts"],
  ]);
  assert.equal(treeHeight(sample()), 2);
  assert.equal(treeHeight(null), -1);
});

test("BST keeps values sorted and ignores duplicates", () => {
  const bst = new BinarySearchTree<number>();
  for (const n of [50, 30, 70, 20, 40, 60, 80]) bst.insert(n);
  assert.deepEqual(bst.inOrder(), [20, 30, 40, 50, 60, 70, 80]);
  assert.equal(bst.insert(60), false);
  assert.equal(bst.size, 7);
  assert.equal(bst.has(60), true);
  assert.equal(bst.has(65), false);
  assert.equal(bst.min(), 20);
  assert.equal(bst.max(), 80);
  assert.equal(bst.height(), 2);
});

test("BST delete handles leaf, one child, and two children", () => {
  const bst = new BinarySearchTree<number>();
  for (const n of [50, 30, 70, 20, 40, 60, 80]) bst.insert(n);
  assert.equal(bst.delete(20), true); // leaf
  assert.equal(bst.delete(30), true); // now has one child (40)
  assert.equal(bst.delete(50), true); // two children (root)
  assert.equal(bst.delete(99), false); // not there
  assert.deepEqual(bst.levelOrder(), [[60], [40, 70], [80]]);
  assert.equal(bst.size, 4);
});

test("sorted input makes a lopsided tree", () => {
  const bst = new BinarySearchTree<number>();
  for (let i = 1; i <= 7; i++) bst.insert(i);
  assert.equal(bst.height(), 6);
});

npx tsx --test

export * from "./bst.ts";

import {
  BinarySearchTree,
  TreeNode,
  levelOrder,
  preorder,
  postorder,
} from "./src/bst.ts";

const bst = new BinarySearchTree<number>();
for (const n of [50, 30, 70, 20, 40, 60, 80]) bst.insert(n);

console.log("sorted:", bst.inOrder().join(" "));
console.log("levels:", JSON.stringify(bst.levelOrder()));
console.log("height:", bst.height());
console.log("has 60:", bst.has(60), "| has 65:", bst.has(65));

bst.delete(30);
console.log("after delete 30:", JSON.stringify(bst.levelOrder()));

const root = new TreeNode("src");
root.add("components").add("Button.tsx");
root.add("index.ts");

const before: string[] = [];
const after: string[] = [];
preorder(root, (v) => before.push(v));
postorder(root, (v) => after.push(v));
console.log("preorder:", before.join(", "));
console.log("postorder:", after.join(", "));
console.log("levels:", JSON.stringify(levelOrder(root)));

npx tsx demo-trees.ts

sorted: 20 30 40 50 60 70 80
levels: [[50],[30,70],[20,40,60,80]]
height: 2
has 60: true | has 65: false
after delete 30: [[50],[40,70],[20,60,80]]
preorder: src, components, Button.tsx, index.ts
postorder: Button.tsx, components, index.ts, src
levels: [["src"],["components","index.ts"],["Button.tsx"]]