Data Structures and Algorithms

Binary Tree.md

Binary Tree

Traverse a Tree

 // Definition for a binary tree node.
 class TreeNode {
     val: number
     left: TreeNode | null
     right: TreeNode | null
     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
         this.val = (val===undefined ? 0 : val)
         this.left = (left===undefined ? null : left)
         this.right = (right===undefined ? null : right)
     }
 }

Preorder Traversal

Recursive solution

Iterative solution

function preorderTraversal(root: TreeNode | null): number[] {
    let stack = root ? [root] : [];
    let result = [];
    while(stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        if(node.right) stack.push(node.right);
        if(node.left) stack.push(node.left);
    }
    return result;
};

Inorder Traversal

Recursive solution

function inorderTraversal(root: TreeNode | null): number[] {
    let result = [];
    if(root) {
        if(root.left) result.push(...inorderTraversal(root.left));
        result.push(root.val);
        if(root.right) result.push(...inorderTraversal(root.right));
    }
    return result; 
};

Iterative solution

function inorderTraversal(root: TreeNode | null): number[] {
    let stack = [], result = [];
    let node = root; 
    while(node || stack.length > 0) {
        while(node) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        result.push(node.val);
        node = node.right;
    }
    return result;
};

Postorder Traversal

Recursive solution

Iterative solution

function postorderTraversal(root: TreeNode | null): number[] {
    let stack = root ? [root] : [];
    let result = [];
    while(stack.length > 0) {
        const node = stack.pop();
        result.unshift(node.val);
        if(node.left) stack.push(node.left);
        if(node.right) stack.push(node.right);
    }
    return result;
};

Dynamic Programming.md

Dynamic Programming

Fibonacci Number

Top-down solution

let F = [0,1];
function fib(n: number): number {
    if(F[n]) return F[n];
    if(n===0) return 0;
    if(n===1) return 1; 
    F[n] = fib(n-2) + fib(n-1);
    return F[n];
};

Bottom-up solution

function fib(n: number): number {
    let F = [0,1];
    for(let i=2; i<=n; i++) {
        F[i] = F[i-2] + F[i-1];
    }
    return F[n];
};

Graph.md

Graph

Undirected graphs

Directed graphs

Weighted graphs