C - Binary trees

This was a partner project in which we learned about the details, advantages, and disadvantages of using trees as data structures. We learned about how to qualify trees as well as how to traverse them. Throughout the project, we implemented binary, binary search, AVL, and Max Binary Heap trees.

Helper File 🙌

• binary_tree_print.c: C function that prints binary trees in a pretty way.

Header File 📁

• binary_trees.h: Header file containing definitions and prototypes for all types and functions written for the project.

Data structures

Basic Binary Tree

/**
 * struct binary_tree_s - Binary tree node
 *
 * @n: Integer stored in the node
 * @parent: Pointer to the parent node
 * @left: Pointer to the left child node
 * @right: Pointer to the right child node
 */
struct binary_tree_s
{
    int n;
    struct binary_tree_s *parent;
    struct binary_tree_s *left;
    struct binary_tree_s *right;
};

typedef struct binary_tree_s binary_tree_t;

Binary Search Tree

typedef struct binary_tree_s bst_t;

AVL Tree

typedef struct binary_tree_s avl_t;

Max Binary Heap

typedef struct binary_tree_s heap_t;

Print function

print_function

                           .----------------------(006)-------.
                      .--(001)-------.                   .--(008)--.
                 .--(-02)       .--(003)-------.       (007)     (009)
       .-------(-06)          (002)       .--(005)
  .--(-08)--.                           (004)
(-09)     (-07)

Tasks

##	File	Description
0	New Node	Write a function that creates a binary tree node
1	Insert left	Write a function that inserts a node as the left-child of another node
2	Insert right	Write a function that inserts a node as the right-child of another node
3	Delete	Function that deletes an entire binary tree
4	Is leaf	Function that checks if a node is a leaf
5	Is root	Write a function that checks if a given node is a root
6	Pre-order traversal	Function that goes through a binary tree using pre-order traversal
7	In-order traversal	Function that goes through a binary tree using in-order traversal
8	Post-order traversal	Function that goes through a binary tree using post-order traversal
9	Height	Function that measures the height of a binary tree
10	Depth	Function that measures the depth of a node in a binary tree
11	Size	Function that measures the size of a binary tree
12	Leaves	Function that counts the leaves in a binary tree
13	Nodes	Function that counts the nodes with at least 1 child in a binary tree
14	Balance factor	Function that measures the balance factor of a binary tree
15	Is full	Function that checks if a binary tree is full
16	Is perfect	Function that checks if a binary tree is perfect
17	Sibling	Function that finds the sibling of a node
18	Uncle	Function that finds the uncle of a node
27	BST - Search	Function that searches for a value in a Binary Search Tree
29	Big O #BST	average time complexities of those operations on a Binary Search Tree: Inserting the value n, Removing the node with the value n, Searching for a node in a BST of size n

Authors:

• Christian Varas | GitHub
• Dany Chavez | GitHub