What you should learn from this project:

• 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

Write a function that creates a binary tree node

• Prototype: binary_tree_t *binary_tree_node(binary_tree_t *parent, int value);
• Where parent is a pointer to the parent node of the node to create
• And value is the value to put in the new node
• When created, a node does not have any child
• Your function must return a pointer to the new node, or NULL on failure

alex@/tmp/binary_trees$ cat 0-main.c
#include <stdlib.h>
#include "binary_trees.h"

/**
 * main - Entry point
 *
 * Return: Always 0 (Success)
 */
int main(void)
{
    binary_tree_t *root;

    root = binary_tree_node(NULL, 98);

    root->left = binary_tree_node(root, 12);
    root->left->left = binary_tree_node(root->left, 6);
    root->left->right = binary_tree_node(root->left, 16);

    root->right = binary_tree_node(root, 402);
    root->right->left = binary_tree_node(root->right, 256);
    root->right->right = binary_tree_node(root->right, 512);

    binary_tree_print(root);
    return (0);
}
alex@/tmp/binary_trees$ gcc -Wall -Wextra -Werror -pedantic binary_tree_print.c 0-main.c 0-binary_tree_node.c -o 0-node
alex@/tmp/binary_trees$ ./0-node
       .-------(098)-------.
  .--(012)--.         .--(402)--.
(006)     (016)     (256)     (512)
alex@/tmp/binary_trees$

Write a function that inserts a node as the left-child of another node

• Prototype: binary_tree_t *binary_tree_insert_left(binary_tree_t *parent, int value);
• Where parent is a pointer to the node to insert the left-child in
• And value is the value to store in the new node
• Your function must return a pointer to the created node, or NULL on failure or if parent is NULL
• If parent already has a left-child, the new node must take its place, and the old left-child must be set as the left-child of the new node.

alex@/tmp/binary_trees$ cat 1-main.c 
#include <stdlib.h>
#include <stdio.h>
#include "binary_trees.h"

/**
 * main - Entry point
 *
 * Return: Always 0 (Success)
 */
int main(void)
{
    binary_tree_t *root;

    root = binary_tree_node(NULL, 98);
    root->left = binary_tree_node(root, 12);
    root->right = binary_tree_node(root, 402);
    binary_tree_print(root);
    printf("\n");
    binary_tree_insert_left(root->right, 128);
    binary_tree_insert_left(root, 54);
    binary_tree_print(root);
    return (0);
}
alex@/tmp/binary_trees$ gcc -Wall -Wextra -Werror -pedantic binary_tree_print.c 1-main.c 1-binary_tree_insert_left.c 0-binary_tree_node.c -o 1-left
alex@/tmp/binary_trees$ ./1-left
  .--(098)--.
(012)     (402)

       .--(098)-------.
  .--(054)       .--(402)
(012)          (128)                                            
alex@/tmp/binary_trees$

• Write a function that inserts a node as the right-child of another node

• Write a function that deletes an entire binary tree

• Write a function that checks if a node is a leaf

• Write a function that checks if a given node is a root

• Write a function that goes through a binary tree using pre-order traversal

• Write a function that goes through a binary tree using in-order traversal

• Write a function that goes through a binary tree using post-order traversal

• Write a function that measures the height of a binary tree

• Write a function that measures the depth of a node in a binary tree

• Write a function that measures the size of a binary tree

• Write a function that counts the leaves in a binary tree

• Write a function that counts the nodes with at least 1 child in a binary tree

• Write a function that measures the balance factor of a binary tree

• Write a function that checks if a binary tree is full

• Write a function that checks if a binary tree is perfect

• Write a function that finds the sibling of a node

• Write a function that finds the uncle of a node

• Write a function that finds the lowest common ancestor of two nodes

• Write a function that goes through a binary tree using level-order traversal

• Write a function that checks if a binary tree is complete

• Write a function that performs a left-rotation on a binary tree

• Write a function that performs a right-rotation on a binary tree

• Write a function that checks if a binary tree is a valid Binary Search Tree

• Write a function that inserts a value in a Binary Search Tree

• Write a function that builds a Binary Search Tree from an array

• Write a function that searches for a value in a Binary Search Tree

• Write a function that removes a node from a Binary Search Tree

• What are the average time complexities of those operations on a Binary Search Tree (one answer per line):

• Write a function that checks if a binary tree is a valid AVL Tree

• Write a function that inserts a value in an AVL Tree

• Write a function that builds an AVL tree from an array

• Write a function that removes a node from an AVL tree

• Write a function that builds an AVL tree from an array

• What are the average time complexities of those operations on an AVL Tree (one answer per line):

• Write a function that checks if a binary tree is a valid Max Binary Heap

• Write a function that inserts a value in Max Binary Heap

• Write a function that builds a Max Binary Heap tree from an array

• Write a function that extracts the root node of a Max Binary Heap

• Write a function that converts a Binary Max Heap to a sorted array of integers

• What are the average time complexities of those operations on a Binary Heap (one answer per line):

• Thomas Graeff - graefft
• Farrukh Akhrarov - narnat