Kevin De Baerdemaeker

Trees

Modified 2023-07-02

Representing a hierarchical tree structure with connected nodes. The root branches out into children, which can have more node as their children.

root

the first parent node

height

longest path from the root, to the deepest child

binary tree

each node has max 2 children, and at least 0, somewhat similar to QuickSort

general tree

tree with 0 or more children

binary search tree

a binary tree with a specific ordering to the nodes

balanced

when left and right children have the same, or close height

branching factor

the amount of children a tree has

Typescript

Traversing the tree yields widely different results depending if you visit the node in the pre, between the two recursives or in the post. 

function walk(curr: BinaryNode<number> | null, path: number[]): number[] {
    if (!curr) return path
    //pre
    path.push(curr.value) // pre_order_search
    //resurse
    walk(curr.left, path)
    //path.push(curr.value) // in_order_search
    walk(curr.right, path)
    // post
    // path.push(curr.value) // post_order_search
    return path
}

export default function pre_order_search(head: BinaryNode<number>): number[] {
    return walk(head, [])
}

Typescript

export default function bfs(head: BinaryNode<number>, needle: number): boolean {
    const q: (typeof head | null)[] = [head]

    while (q.length) {
        const curr = q.shift()
        if (!curr) {
            continue
        }

        //search
        if (curr?.value === needle) {
            return true
        }

        q.push(curr.left)
        q.push(curr.right)
    }

    return false
}

Binary Tree Comparison

export default function compare(a: BinaryNode<number> | null, b: BinaryNode<number> | null): boolean {
    if (a === null && b === null) {
        return true
    }

    if (a === null || b === null) {
        return false
    }

    if (a.value !== b.value) {
        return false
    }

    return compare(a.left, b.left) && compare(a.right, b.right)
}

Depth-First Search on Binary Tree

function search(curr: BinaryNode<number> | null, needle: number): boolean {
    if (!curr) return false
    if (curr.value === needle) return true
    if (curr.value < needle) {
        return search(curr.right, needle)
    }
    return search(curr.left, needle)
}

export default function dfs(head: BinaryNode<number>, needle: number): boolean {
    return search(head, needle)
}

References

Backlinks