### Binary Search Trees

| Operations | Array (unsorted) | Array (sorted) | Linked List | Binary Search Tree(balanced) | Hash Table |
|------------------ |------------------ |----------------------- |--------------------------------------- |------------------------------ |------------ |
| Search | O(n) | O(logn) binary search | similar to array, sorted and unsorted | O(logn) | O(1) |
| Insert | O(1) | O(n) | | O(logn) | O(1) |
| Delete | O(n) | O(n) | | O(logn) | O(1) |
| Find Closest | O(n) | O(logn) binary search | | O(logn) | O(n) |
| Sorted Traversal | O(nlogn) | O(n) | | O(n) | O(nlogn) |

- Data is organized in binary search tree in such a way while searching a item nearly half of items are skipped in every step. it is inspited from binary search
- For every node, all keys in left side of the subtree are smaller and keys in the right side of the sub tree are bigger
- All keys are typically consided distinct but we can update the logic so the left is less or equal to root or right can be bigger or equal to root
- Note: if elements are not distinct we cannot determine if we need to traverse left or right
- Data type support
- Support negative values
- Support fractions
- Support charecters
- Not cache frendly
- C++ map, set, multimap, multiset. Java - TreeMap, TreeSet
- python ordered dict?
- Operations
- Create empty bst
- Insert
- Delete
- BST will form a chain like linked list if items are in increasing or decreasing order

### Operations
- Search - O(h)
- Ceil - O(h)
- Floor - O(h)
- Insert - O(h)
- Delete - O(h)
- Finding greater - O(h)
- Finding smaller - O(h)
- Search - O(h)
- Iterative - TC: O(h) SC: O(1)
- Recursive - TC: O(h) SC: O(h)
for bst h --> n in worst case
- Insert - O(h) [for bst h --> n in worst case]
- item exist already dont do anything
- insert will replace the root if root is already empty
- insert operation will always place nodes at leaf
- Iterative - TC: O(h) SC: O(1)
- Delete - O(h)
- item doesnt exist dont do any thing
- item is left node
- item contains either left or right node
- item contains both left and right node - BST property needs to be maintained
- replace the deleted value with either closest smaller or greater value
- clue: next greater value would be inorder succesor
- if item contains only one item that will be deleted then return null
- Self balancing binary search tree - inblanced bst it become O(logn)

### Applications
- K Dimentional Tree or KD Tree (https://www.geeksforgeeks.org/k-dimensional-tree/)
- Maintain sorted stream of data (or sorted set of data)
- Implement doubly ended priority queue
- Solve Problems like
- Count smaller/greater in a stream
- Floor/Ceiling/Greater/Smaller in a stream

### Problems
- Search in BST
- Iterative
- Recursive
- Insert in BST
- Iterative
- Recursive
- Delete in BST
- Iterative
- Recursive
- Floor in BST
- Iterative
- Recursive
- Ceil in BST
- Iterative
- Recursive
- Self Balancing BST
- AVL Tree
- Red Black Tree
- Ceiling on left side in an array
- Find Kth smallest element
- Check for BST
- Fix BST with two nodes swapped
- pair sum in BST
- Vertical sum in BST
- Vertical Traversal of BST
- Top view of binary tree
- Bottom view of binary tree
- find the inorder succsor of the node -> which is smallest key greater than the current key - useful during delete operation in BST
- Finding elements in bst
- minimum element in BST
- traverse left always and return the data of the node whose left child is None
- max element in BST
- traverse right always and return the data of the node whose right child is None
- Traversal
- Concepts
- Inorder (left, root, right) -> order the elements in assensding order
- Preorder (root, left, right)
- PostOrder (left, right, root)
- Reverse of Inorder(right, root, left) -> order the elemets in reverse order
- Problems
- Inorder traversal
- is given array is Inorder traversal of BST
- it gives sortered array
- special cases
- handle for reverse order

            def is_inorder(arr):    
                prev = None
                for i in range(1, len(arr)):
                    current_diff = arr[i] - arr[i - 1]
                    if prev is None or (prev < 0 and current_diff < 0) or (prev > 0 and current_diff > 0):
                        prev = current_diff
                    else:
                        return False
                
                return True

- Query
- Finding Element - Use bst property to quickly find the items needed
- search a node in bst
- print bst's in given range
- kth smallest element in bst
- kth largest elemtn in BST
- c=[0] is passed by reference to keep track of counter

        def kth_largest_element(node, k, c):
            if node == None:
                return None
            
            result = kth_largest_element(node.right, k, c)
            if result is not None:
                return result


            c[0] += 1

            if c[0] == k:
                return node.data

            result = kth_largest_element(node.left, k, c)
            if result is not None:
                return result

- find a pair with given target sum in BST
- using hashing
- without hashing two pointer approach
- sum of leaf nodes in bst

- Construction
- Sorted array to balanced bst
- check for BST
- root node can have any value from (-sys.maxsize - 1) to (sys.maxsize)
- and value in left sub tree is between (-sys.maxsize - 1) to node.val
- and value in right sub tree is between node.val to (sys.maxsize)

        def check_bst(node, min_val = -sys.maxsize - 1, max_val = sys.maxsize):
            if node is None:
                return True
            
            
            result = node.data > min_val and node.data < max_val

            if node.left is not None:
                result = result and check_bst(node.left, min_val, node.data) 

            if node.right is not None:
                result = result and check_bst(node.right, node.data, max_val)

            return result

- above solution will work for fractions
- need some moditions to support strings
- insert a node in BST

def insert(root, data):
    if root is None:
        return Node(data) 

    # avoid duplicate
    if root.data == data:
        return root

    if root.data > data:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)

    return root

- Normal bst to balanced bst
- Construct bst from postorder
- pre order to post order
- count bst nodes that lie in an given range
- brothers from different roots
- Add all greater nodes to every node in a bst
- lowest common ancestor in an bst
- is binary tree a heap
- binary tree to bst
- fixing two nodes of bst
- merge two bst's
- find common nodes in two bst's
- find closest element in bst
- pairs voilating the bst property
- delete nodes greater than k
- Triplet with zero sum in BST
- Predecessor and sucessor
- Median in BST
- Unique BST
- Closest Neighbor in BST
- PreOrder Traversal in BST
- InOrder Sucessor in BST
- Change of Key in BST
- Check wether bst contains dead end
- delete a node from BST
- AVL Tree insertion
- pth common ancestor in BST
- Largest BST
- does array represent heap
- optimal binary search tree
- Print leaf nodes from preorder traversal of BST
- remove bst key outside given range
- Maximum product of Increasing subsequence of size 3
- Sum of K smallest elements in BST
- Easy Query
- Sorted linked list to BST
- maximum sum leaf to root path
- BST to greater sum tree
- BST to max heap