Untitled

```bash
chmod +x katapault-launcher-1-0-all.deb
chmod +x run_docker.sh
sudo apt-get install -f ./katapault-launcher-1-0-all.deb
sudo apt install docker.io
```
### Dynamic arrays
- In C we have static arrays fixed size, memory ahead of array can be used by some other process, so we cant expand the array.
- In C++ we have 'vectors' and in java we have 'array_list' which are dynamic size array, whose size can be increased as and when needed.
- In Dynamic arrays when the array gets filled up, new space is allocated to array (double of previous space), and previous array is copied in this new space then old space is freed.
  - best case insertion : O(1)
  - worst case insertion : O(n), (for copying elements)

### Arrays vs linked list.
- Arrays are indexed, element access : O(1).
- linked list uses pointers, element access : O(n).
- Array uses static or heap memory.
- Linkedlist uses dynamic heap memory.
- Linkedlist needs more space to store pointers to next node.

## linear search : O(n) time and O(1) space.
## Binary search :
- can search key in array in O(log n) time and O(1) space, if the array is sorted.

```c
# include<stdio.h>

int binary_search(int arr[], int size, int key){
    int start = 0, end = size-1, mid;
    while(start <= end){
        mid = start + (end - start) / 2; // calculate mid index
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key) // search in right subarray
            end = mid - 1;
        else //search in left subaray 
            start = mid + 1;        
    }
    return -1;   
}
int main()
{
    int arr[8] = {1,2,3,4,5,6,7,8};
    int pos = binary_search(arr, 8, 9);
    if(pos != -1)
        printf("Element found at index : %d.\n", pos);
    else
        printf("Element not found.\n");
}
```
- binary search will not work well for LL, due to no random access to calculate mid.

## Binary search trees
- `root node` : head node
- `leaf nodes` : dont have `child nodes`.
- each node can have a left child node and a right child node.
- `internal node` : every node aside leaf nodes.
- `subtree` : tree created by a child node, can be `left subtree` or `right subtree`.
- each node can have 2 child, 1 left child, 1 right child or no child. but cannot have more than 1 child.
- An `n-ary tree` can have atmost n childrens, A binary tree can have atmost 2 childrens.
- `Depth of a tree` is maximum depth of any node (leaf node), Root node is at depth 0.  
- `balanced tree` : for any node depth of left subtree and depth of right subtree do not differ by more than 1 then it is called balanced tree. It provides optimal searching.

- **Binary search tree** is a special tree in which for all nodes
  1. all the nodes in left subtree are less than parent node.
  2. all the nodes right subtree are greater than parent node.

- Binary search tree is highly dependent on the order of sequence.
- depth of balanced binary search tree = log(n).
- depth of skewed tree = n.   

### Implementation using pointers/references.
- Each node contains
  1. pointer to left child.
  2. stored data
  3. pointer to right child.

### Implementation using arrays.
- for a 1 based indexed array.
- put root at index 1
- for a root at index i.
  - put left child at index 2*i
  - put right child at index 2*i+1
- It will store whole tree as a BFS traversal.
- Drawbacks : some space is wasted, for a highly unbalanced binary search tree(skewed tree), if we want to store at tree of depth 6, we need 63 array space.
- so for balanced search tree we can use arrays, but for skewed trees, use pointers and nodes.

### Building a BST for a sequence
- build a BST by satisfying basic property of BST, put first element at root, small element at left, greater or equal element at right.
- ascending or descending sequence creates a highly skewed tree.

- Time complexity to insert a new element in BST 
  - Best case : O(log n) 
  - worst case : O(n) , n-1 comparisions.

### Operations on BST
### Search
```c
node* search_recursively(node* head, int key){
    if(head == NULL || head->data == key)
        return head;
    if (key < head->data) //search left subtree
        return search_recursively(key, head->left);
    else                  //search right subtree
        return search_recursively(key, head->right);
}
```
### Minimum element
```c
int get_minimum(node* head){
    node* curr = head;
    while(curr->left != NULL){
        curr = curr->left;
    }
    return curr->data;
}
```
### Maximum element
```c
int get_maximum(node* head){
    node* curr = head
    while(curr->right != NULL){
        curr = curr->right;
    }
    return curr->data;
}
```
### Insert element
```c
node* insert_node(node* head, int info){
    node* temp;
    temp->data = info;
    temp->left = NULL;
    temp->right = NULL;
    if(head == NULL)
        return temp;
    node* curr = head;
    while(curr != NULL){
        if(curr->data > info ){
            if(curr->left == NULL){
                curr->left = temp;
                break;
            } 
            curr = curr->left;
        }
        else if(curr->data < info){
            if(curr->right == NULL){
                curr->right = temp;
                break;
            } 
            curr = curr->right;
        }
    }
}
```
### Traversal : O(n)
1. Inorder : left node, root node, right node.(recursively)
2. Preorder : root node, left node, right node.(recursively)
3. Postorder : left node, right node, root node.(recursively)
- Inorder traverasal gives us sorted array.
- inorder : 4,6,8,12,16,18.
  - 8 is `inorder predecessor` of 12.
  - 14 is `inorder successor` of 12.
- similarly we can have preorder predecessor/successor and postorder predecessor/successor.

- the inorder traversal of expression tree gives us infix expression.
- the preorder traversal of expression tree gives us prefix expression.
- the postorder traversal of expression tree gives us postfix expression.

### Delete
- pointer to node is given that is to be deleted.
- if the node is leaf node, deallocate the memory, adjust the NULL pointer for its parent.
- if the node has one child, 


> saurabh