Skip to content

Instantly share code, notes, and snippets.

@dobeerman

dobeerman/binaryTree.ts

Created October 15, 2021 19:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dobeerman/698680922ec18bcd84a22668cf821a99 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dobeerman/698680922ec18bcd84a22668cf821a99 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dobeerman created this gist Oct 15, 2021.
    116 changes: 116 additions & 0 deletions binaryTree.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,116 @@
    class TreeNode {
    public value: number;
    public left!: TreeNode;
    public right!: TreeNode;

    constructor(value: number) {
    this.value = value;
    }
    }

    type Method = "preOrder" | "inOrder" | "postOrder";

    class BinaryTree {
    public root: TreeNode;

    constructor(value: number) {
    this.root = new TreeNode(value);
    }

    public add(value: number) {
    const newNode = new TreeNode(value);

    if (!this.root) {
    this.root = newNode;
    return;
    }

    let currentNode = this.root;

    while (currentNode) {
    if (newNode.value < currentNode.value) {
    if (!currentNode.left) {
    currentNode.left = newNode;
    return;
    }

    currentNode = currentNode.left;
    } else {
    if (!currentNode.right) {
    currentNode.right = newNode;
    return;
    }

    currentNode = currentNode.right;
    }
    }
    }

    public traverseDFS(method: Method, callback: (node: TreeNode) => void) {
    switch (method) {
    case "preOrder":
    return this.preOrder(this.root, callback);
    case "inOrder":
    return this.inOrder(this.root, callback);
    default:
    return this.postOrder(this.root, callback);
    }
    }

    public traverseBFS(callback: (node: TreeNode) => void) {
    const queue = [this.root];

    while (queue.length) {
    const node = queue.shift()!;
    callback(node);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
    }
    }

    private preOrder(node: TreeNode, callback: (node: TreeNode) => void) {
    if (!node) return;

    callback && callback(node);
    this.preOrder(node.left, callback);
    this.preOrder(node.right, callback);
    }

    private inOrder(node: TreeNode, callback: (node: TreeNode) => void) {
    if (!node) return;

    this.preOrder(node.left, callback);
    callback && callback(node);
    this.preOrder(node.right, callback);
    }

    private postOrder(node: TreeNode, callback: (node: TreeNode) => void) {
    if (!node) return;

    this.preOrder(node.left, callback);
    this.preOrder(node.right, callback);
    callback && callback(node);
    }
    }

    const tree = new BinaryTree(8);

    tree.add(7);
    tree.add(9);
    tree.add(5);
    tree.add(10);
    tree.add(20);
    tree.add(6);
    tree.add(2);
    tree.add(11);

    // 8
    // 7 9
    // 5 10
    // 2 6 20
    // 11

    // tree.traverseDFS("preOrder", (node: TreeNode) => { console.log(node.value) })
    tree.traverseBFS((node: TreeNode) => {
    console.log(node.value);
    });