bst.js

var node = {
    value: 0,
    left: null,
    right: null
}

var create_node = function(val, l, r) {
    return {value: val, left: l, right: r}
}


var n3 = {
    value: 15,
    left: null,
    right: null
}
var n2 = {
    value: 13,
    left: null,
    right: n3
}
var n1 = {
    value: 5,
    left: null,
    right: null
}
var n0 = {
    value: 10,
    left: n1,
    right: n2
}

console.log('tree: ', n0)

function print_tree(root) {
    if (root != null) {
        print_tree(root.left)
        console.log(root.value)
        print_tree(root.right)
    }
}


function find(k, root) {
    // base
    if (root != null) {
        if (root.value == k) {
            return root
        } else if (k < root.value) {
            return find(k, root.left)
        } else {
            return find(k, root.right)
        }
    } else {
        return null
    }
}

function pretty_print(root) {
    if (root != null) {
        console.log(root.value)
    }
}

function insert(k, root) {
    // base case
    if (root.left === null && k < root.value) {
        root.left = {
            value: k,
            left: null,
            right: null,
        }
        return
    }
    if (root.right === null && k > root.value) {
        root.right = {
            value: k,
            left: null,
            right: null,
        }
        return
    }

    // recursive case
    if (k < root.value) {
        insert(k, root.left)
    } else if (k > root.value) {
        insert(k, root.right)
    }
}

function test_insert() {
    insert(8, n0)
    insert(9, n0)
    print_tree(n0)
    console.log(n0)
}


function delete_node(k, root, parent) {
    if (k < root.value) {
        // left
        console.log('go left')
        delete_node(k, root.left, root)
    } else if (k > root.value) {
        // right
        console.log('go right')
        delete_node(k, root.right, root)
    } else {
        console.log('time to delete')
        // base
        if (root.left === null && root.right === null) {
            // 1. no children
            if (root.value < parent.value) {
                parent.left = null
            } else {
                parent.right = null
            }
        } else if (root.left !== null && root.right !== null) {
            // 2. two children
            console.log('two children')

            // find successor
            var current_parent = root
            var current = root.right
            while (current.left !== null) {
                current_parent = current
                current = current.left
            }
            console.log('current: ', current)

            // delete successor and attach successor's children
            if (current_parent == root) {
                current_parent.right = current.right
            } else {
                current_parent.left = current.right
            }

            // swap successor and delete root
            current.left = root.left
            current.right = root.right
            if (parent !== null) {
                if (root.value < parent.value) {
                    parent.left = current
                } else {
                    parent.right = current
                }
            }

            // replace root
            root = current
            console.log('done')
        } else {
            // 3. one child
            console.log('one child')
            if (root.left !== null && root.right === null) {
                if (root.value < parent.value) {
                    parent.left = root.left
                } else {
                    parent.right = root.left
                }
            } else if (root.left === null && root.right !== null) {
                if (root.value < parent.value) {
                    parent.left = root.right
                } else {
                    parent.right = root.right
                }
            }
        }
    }
    return root
}

function test_delete_node() {
    var new_tree = delete_node(10, n0, null)
    console.log(new_tree)
    print_tree(new_tree)
}

console.log('test_delete_node')
test_delete_node()