# Binary Trees and Heaps: Implementation in Java

## Binary Trees

### First Element

The `first()`

method returns the first element in the binary tree by recursively traversing the left subtree until it reaches the leftmost node.

### Last Element

The `last()`

method returns the last element in the binary tree by iteratively traversing the right subtree until it reaches the rightmost node.

### Add Element

The `add(E item)`

method adds an element to the binary tree while maintaining its sorted order. It first checks if the element already exists and returns `false`

if it does. Otherwise, it traverses the tree, comparing the new element with the current node’s data. If the new element is smaller, it moves to the left subtree; if it’s larger, it moves to the right subtree. When it reaches a null node, it inserts the new element there and updates the size of the tree.

### Contains Element

The `contains(Object arg0)`

method checks if an element exists in the binary tree. It recursively traverses the tree, comparing the target element with the current node’s data. If they are equal, it returns `true`

. If the target element is smaller, it moves to the left subtree; if it’s larger, it moves to the right subtree. If it reaches a null node, it returns `false`

.

### Remove Element

The `remove(Object arg0)`

method removes an element from the binary tree while maintaining its sorted order. It recursively searches for the element to remove. If it finds the element, it handles three cases: 1) If the node has two children, it replaces the node’s data with the minimum element from the right subtree and recursively removes the minimum element. 2) If the node has only a left child, it replaces the node with its left child. 3) If the node has only a right child or no children, it replaces the node with its right child or null, respectively.

### Ceiling Element

The `ceiling(E e)`

method finds the smallest element in the binary tree that is greater than or equal to the given element `e`

. It traverses the tree, keeping track of the maximum element found so far that is less than or equal to `e`

. If it finds an element equal to `e`

, it returns that element. Otherwise, it returns the maximum element found during the traversal.

## Heaps

### Sink Operation

The `sink(int parent)`

method is used to maintain the heap property in a min-heap. It compares the parent node with its children and swaps it with the smaller child if necessary. This process is repeated recursively until the heap property is restored.

### Floating Operation

The `floating(int child)`

method is used to maintain the heap property in a min-heap after inserting a new element. It compares the child node with its parent and swaps them if the child is smaller. This process is repeated recursively until the heap property is restored.

### Heapify Operation

The `heapify()`

method transforms an array into a min-heap by calling the `sink()`

method on all non-leaf nodes in reverse order.

### IndexOf Operation

The `indexOf(E item, int current)`

method searches for an element in the heap and returns its index. It recursively traverses the heap, comparing the target element with the current node’s data. If they are equal, it returns the current index. If the target element is smaller, it moves to the left subtree; if it’s larger, it moves to the right subtree. If it reaches a null node or the target element is not found, it returns -1.

### Add Element

The `add(E item)`

method adds an element to the heap while maintaining the heap property. It inserts the new element at the end of the heap and then calls the `floating()`

method to restore the heap property.

### Remove Element

The `remove(E item)`

method removes an element from the heap while maintaining the heap property. It first finds the index of the element using the `indexOf()`

method. If the element is found, it swaps it with the last element in the heap, decreases the size of the heap, and then calls either the `sink()`

or `floating()`

method to restore the heap property.

### Grow Operation

The `grow()`

method doubles the capacity of the heap when it becomes full. It creates a new array with twice the capacity, copies the elements from the old array to the new array, and updates the data array reference.