Binary Search Tree | Subset of Binary Tree

Binary search tree is great for searching or comparing things?

We know using a hash-table we have O(1) for look up, then why study Binary Search Tree?

Why is this better than hash table?

Binary search tree preserves relationships, just like you would not want your folders to be in hash table data structure, because there is no sort of relationship instead we want our folder to have a relationship.

  Parent>MyPc> DriveA > MyDataStructure>Code

Things like binary search tree allow us to preserve the realtionship.

                       101
                33            105
            9        37  104        144   

Binary Search Trees (BST) offer unique advantages that make them indispensable in certain scenarios.

1. Ordered Data: BST maintain natural order of elements due to their structure. This makes them ideal for operations like:
2. Finding minimum or maximum value in O(logn) time.
3. Retrieving elements in sorted order through in order traversal.
4. Finding the 4rth smallest element/largest element efficiently
5. Range Based Queries:
6. BST are perfect for range-based queries. For eg: find all keys between 50 & 100. i.e O(k + log n), k is number of keys in the range.
7. Memory Efficiency: It uses node based structure, no extra memory is preallocated. Only the memory is allocated for node.

Rules:

1. All Child nodes to the right must be greater than current node.
2. All child nodes to the left must be smaller than current node.
3. Node can only have up-to two child.

Time Complexity:

Lookup : O(logN)

Insert : O(logN)

Delete : O(logN)

Problem with binary search tree:

Can become a linked list, where nodes are just added by looping through node on the right.

                2
            1      5
    

if we insert 6, 7, 8, 9, 10

            2
        1       5
                    6
                        7
                            8
                                9
                                    10

Unbalanced Binary Search Tree is Bad, Ideally we want to balance our search tree.

Performance Implications:

1. It has really good performance across the board. Most or all operation in binary search tree is better than O(N) assuming it's balanced.
2. Binary search tree are not the fastest of anything. On average an array or an obj will have faster operation

As long as you stay away from edge cases, Binary search tree performs really well.

Two ways we can do tree traversal:

1. Depth First Search (DFS)
2. PreOrder: Grab nodes as you go
3. InOrder: Go down one direction then hit, null, come back grab it's parent.
4. PostOrder: Go down both direction then hit null on both direction, then grab it's parent.
5. Breadth First Search

Depth First Search (DFS)

function preOrder(node, result =[]){
    if(!node){
        return
    }
    result.push(node.value)
    preOrder(node.left, result)
    preOrder(node.right, result)
    return result
}

function inOrder(node, result = []){
    if(!node){
        return
    }
    inOrder(node.left, result)
    result.push(node.value)
    inOrder(node.right, result)
    return result
}

function postOrder(node, result = []){
    if(!node){
        return
    }
    postOrder(node.left, result)
    postOrder(node.right, result)
    result.push(node.value)
    return result
}

Breadth First Search

function bfs(node){
    if(!node){
        return []
    }
    const queue = []
    queue.push(node)
    const result = []

    while(queue.length > 0){
        let currentNode = queue.shift()
        result.push(currentNode.value)

        currentNode.left && queue.push(currentNode.left)
        currentNode.right && queue.push(currentNode.right)

    }
    return result
}