Amili-usain/binary_trees

Binary trees

Learning Objectives

What is a binary tree
What is the difference between a binary tree and a Binary Search Tree
What is the possible gain in terms of time complexity compared to linked lists
What are the depth, the height, the size of a binary tree
What are the different traversal methods to go through a binary tree
What is a complete, a full, a perfect, a balanced binary tree

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;

File/Folder	Description
tests	Folder of test files for all tasks
binary_tree_print.c	Helper file provided for the project by alx A function that prints binary trees in a pretty way.
binary_trees.h	Header file containing definitions and prototypes for all types and functions written for the project.
0-binary_tree_node.c	A function that creates a binary tree node with a given parent and value. Returns a pointer to the new node, or NULL on failure.
1-binary_tree_insert_left.c	A function that inserts a node as the left-child of another. Returns a pointer to the new node, or NULL on failure. If the given parent already contains a left node, the new node takes its place and the old left-child becomes the left-child of the new node.
2-binary_tree_insert_right.c	A function that insert a node as the right-child of another. Returns a pointer to the new node, or NULL on failure. If the given parent already contains a right node, the new node takes its place and the old right-child becomes the right-child of the new node.
3-binary_tree_delete.c	A function that deletes an entire binary tree.
4-binary_tree_is_leaf.c	A function that checks if a given node is a leaf. Returns 1 if the node is a leaf, 0 otherwise.
5-binary_tree_is_root.c	A function that checks if a given node is a root. Returns 1 if the node is a root, 0 otherwise.
6-binary_tree_preorder.c	A function that traverses a tree using pre-order traversal.
7-binary_tree_inorder.c	A function that traverses a tree using in-order traversal.
8-binary_tree_postorder.c	A function that traverses a tree using post-order traversal.
9-binary_tree_height.c	A function that returns the height of a binary tree.
10-binary_tree_depth.c	A function that returns the depth of a given node in a binary tree.
11-binary_tree_size.c	A function that returns the size of a binary tree.
12-binary_tree_leaves.c	A function that returns the number of leaves in a binary tree.
13-binary_tree_nodes.c	A function that returns the number of nodes in a binary tree with at least one child.
14-binary_tree_balance.c	A function that returns the balance factor of a binary tree.
15-binary_tree_is_full.c	A function that checks if a binary tree is full. Returns 1 if a tree is full, 0 otherwise.
16-binary_tree_is_perfect.c	A function that checks if a binary tree is perfect. Returns 1 if a tree is perfect, 0 otherwise.
17-binary_tree_sibling.c	A function that returns a pointer to the sibling of a given node in a binary tree. Returns NULL if no sibling is found.
18-binary_tree_uncle.c	A function that returns a pointer to the uncle of a given node in a binary tree. Returns NULL if no uncle is found.
100-binary_trees_ancestor.c	A function that returns a pointer to the lowest common ancestor node of two given nodes in a binary tree. Returns NULL if no common ancestor is found.
101-binary_tree_levelorder.c	A function that traverses a binary tree using level-order traversal.
102-binary_tree_is_complete.c	A function that checks if a binary tree is complete. Returns 1 if the tree is complete, 0 otherwise.
103-binary_tree_rotate_left.c	A function that performs a left-rotation on a binary tree. Returns a pointer to the new root node of the tree after rotation.
104-binary_tree_rotate_right.c	A function that performs a right-rotation on a binary tree. Returns a pointer to the new root node of the tree after rotation.
110-binary_tree_is_bst.c	A function that checks if a binary tree is a valid binary search tree. Returns 1 if the tree is a valid BST, 0 otherwise.
111-bst_insert.c	A function that inserts a value into a binary search tree. Returns a pointer to the new node, or NULL on failure. If the tree is NULL, the value becomes the root node. The value is ignored if it is already present in the tree.
112-array_to_bst.c	A function that builds a binary search tree from an array. Returns a pointer to the root node of the created tree, or NULL on failure.
113-bst_search.c	A function that searches for a value in a binary search tree. If the value is matched in the BST, returns a pointer to the matched node. Otherwise, returns NULL.
114-bst_remove.c	A function that removes a node from a binary search tree. Returns a pointer to the new root node of the tree after deletion. If the node to be deleted has two children, it is replaced with its first in-order successor.
115-O	A file containing the average time complexities of binary search tree operations (one answer per line): Inserting the value n. Removing the node with the value n. Searching for a node in a BST of size n.
120-binary_tree_is_avl.c	A function that checks if a binary tree is a valid AVL tree. If the tree is a valid AVL tree, returns 1. Otherwise, returns 0.
121-avl_insert.c	A function that inserts a value in an AVL tree. Returns a value to the inserted node, or NULL on failure.
122-array_to_avl.c	A function that builds an AVL tree from an array. Returns a pointer to the root node of the created AVL tree, or NULL on failure. Ignores duplicate values.
123-avl_remove.c	A function that removes a node from an AVL tree Returns pointer to the new root node of the tree after removing the desired value, and after rebalancing If the node to be deleted has two children, it is replaced with its first in-order successor (not predecessor)
124-sorted_array_to_avl.c	A function that builds an AVL tree from an array. Ignores duplicate value in the array Returns pointer to the root node of the created AVL tree, or NULL on failure
125-O	Text file containing the average time complexities of AVL tree operations (one answer per line): Inserting the value n. Removing the node with the value n. Searching for a node in an AVL tree of size n.
130-binary_tree_is_heap.c	A function that checks if a binary tree is a valid Max Binary Heap Returns 1 if tree is a valid Max Binary Heap, and 0 otherwise If tree is NULL, return 0
131-heap_insert.c	A function that inserts a value in Max Binary Heap Returns pointer to the created node, or NULL on failure Follows a max Heap ordering.
132-array_to_heap.c	A function that builds a Max Binary Heap tree from an array Returns pointer to the root node of the created Binary Heap, or NULL on failure
133-heap_extract.c	A function that extracts the root node of a Max Binary Heap Returns the value stored in the root node and 0 on failure
134-heap_to_sorted_array.c	A function that converts a Binary Max Heap to a sorted array of integers size is assumed a valid address Returns array sorted in descending order
135-O	Text file containing the average time complexities of binary heap operations (one answer per line): Inserting the value n. Extracting the root node. Searching for a node in a binary heap of size n.

Authors ✒️

• Mugigayi Amili Hussein <Amili-usain>