Binary Search Tree (BST)

A binary tree is a tree data structure in which each node has at most two children as left and right. A binary search tree (BST) is a binary tree with the properties:

• all the nodes to the left of any node are lesser
• all the nodes to the right of any node are greater

BT and BST are basic tree data structures but still PIE would make a very bold statement - "Without going into too much detail (as the special cases get very nasty), it is also possible to delete and insert into a balanced BST in O(logn) time."

search: O(logn)

bool searchBST(Node root, int value):
    if root = null:
        return false
    if root.value = value:
        return true
    if value < root.value:
        return searchBST(root.left, value)
    else if value > root.value:
        return searchBST(root.right, value)

insert: O(logn)

void insertBST(Node root, int value):
    Node node = new Node(value)
    insertBST(root, node)

void insertBST(Node root, Node node):
    if node.value < root.value: 
        if root.left != null: 
            insertBST(root.left, node) 
        else: 
            root.left = node 
    else if node.value > root.value:
        if root.right != null: 
            insertBST(root.right, node)
        else:
            root.right = node

delete: O(logn)
There are three cases in delete:
- if node is a leaf (no child): assign null to node's parent pointer
- if node has one child (left or right): assign node's child to node's parent pointer
- if node had two children: assign node's right child to node's parent pointer, assign node's left child to the leftmost successor of the node's right child.

void deleteBST(ref Node root, Node node):
    Node parent = getParent(root, node) //O(logn)

    //case 1: no child
    if node.left == null && node.right == null: 
        if node == root: // parent is null
            root = null
        else:
            if parent.left == node:
                parent.left = null
            else: //parent.right == node
                parent.right = null
    
    //case 2: right child
    else if node.left == null && node.right != null: 
        if node == root: // parent is null
            root = node.right
        else:
            if parent.left == node:
                parent.left = node.right
            else: //parent.right == node
                parent.right = node.right
        // remove reference
        node.right = null
    
    //case 3: left and right children
    else if node.left != null && node.left != null:
        // node's left sub-tree goes to left-most child of node's right child
        // successor is left-most of node's right child
        Node successor = node.right
        while successor.left != null:
            successor = successor.left 
        successor.left = node.left
        
        if node == root: // parent is null
            root = node.right
        else:
            if parent.left == node:
                parent.left = node.right
            else: //parent.right == node
                parent.right = node.right
        
        // remove references
        node.right = null
        node.left = null

One thing to note is that the "special cases get very nasty" :D. In each case, if the node is a root we have to maintain root variable (case 1: null, case 2a: right child (2b: left child), case 3: right child).


[Hat tip to JE]