richie-omondi/binary_trees

This repo contains functions written in C that build different types of binary trees and implement various operations on them

Binary trees

This project has been done to learn about what is a binary tree, the different traversal methods to go through a binary tree, and the different types of binary trees (complete, full, perfect, and balanced).

Technologies

• Scripts written in Bash 4.4.23(1)
• C files are compiled using gcc 6.3.0
• Tested on Ubuntu 20.04 LTS

Files

Filename	Description
0-binary_tree_node.c	Function that creates a binary tree node
1-binary_tree_insert_left.c	Function that inserts a node as the left-child of another node
2-binary_tree_insert_right.c	Function that inserts a node as the right-child of another node
3-binary_tree_delete.c	Function that deletes an entire binary tree
4-binary_tree_is_leaf.c	Funciton that checks if a node is a leaf
5-binary_tree_is_root.c	Function that checks if a given node is a root
6-binary_tree_preorder.c	Function that goes through a binary tree using pre-order traversal
7-binary_tree_inorder.c	Function that goes through a binary tree using in-order traversal
8-binary_tree_postorder.c	Function that goes through a binary tree using post-order traversal
9-binary_tree_height.c	Function that measures the height of a binary tree
10-binary_tree_depth.c	Function that measures the depth of a node in a binary tree
11-binary_tree_size.c	Funciton that measures the size of a binary tree
12-binary_tree_leaves.c	Function that counts the leaves in a binary tree
13-binary_tree_nodes.c	Function that counts the nodes with at least 1 child in a binary tree
14-binary_tree_balance.c	Function that measures the balance factor of a binary tree
15-binary_tree_is_full.c	Function that checks if a binary tree is full
16-binary_tree_is_perfect.c	Function that checks if a binary tree is perfect
17-binary_tree_sibling.c	Function that finds the sibling of a node
18-binary_tree_uncle.c	Function that finds the uncle of a node
100-binary_trees_ancestor.c	Funciton that finds the lowest common ancestor of two nodes
101-binary_tree_levelorder.c	Function that goes through a binary tree using level-order traversal
102-binary_tree_is_complete.c	Function that checks if a binary tree is complete
103-binary_tree_rotate_left.c	Function that performs a left-rotation on a binary tree
104-binary_tree_rotate_right.c	Function that performs a right-rotation on a binary tree
110-binary_tree_is_bst.c	Function that checks if a binary tree is a valid Binary Search Tree
111-bst_insert.c	Function that inserts a value in a Binary Search Tree
112-array_to_bst.c	Function that builds a Binary Search Tree from an array
113-bst_search.c	Function that searches for a value in a Binary Search Tree
114-bst_remove.c	Function that removes a node from a Binary Search Tree
115-O	File with the average time complexities of inserting a value, removing and searching a node on a Binary Search Tree
120-binary_tree_is_avl.c	Function that checks if a binary tree is a valid AVL Tree
121-avl_insert.c	Function that inserts a value in an AVL Tree
122-array_to_avl.c	Function that builds an AVL tree from an array
123-avl_remove.c	Function that removes a node from an AVL tree
124-sorted_array_to_avl.c	Function that builds an AVL tree from an array
125-O	File with the average time complexities of inserting a value, removing and searching a node on a AVL Tree
130-binary_tree_is_heap.c	Function that checks if a binary tree is a valid Max Binary Heap
131-heap_insert.c	Function that inserts a value in Max Binary Heap
132-array_to_heap.c	Function that builds a Max Binary Heap tree from an array
133-heap_extract.c	Write a function that extracts the root node of a Max Binary Heap
134-heap_to_sorted_array.c	Write a function that converts a Binary Max Heap to a sorted array of integers
135-O	File with the average time complexities of inserting a value, removing and searching a node on a Binary Heap

Author

• Richard Orido