/holbertonschool-binary_trees

Primary LanguageC

Binary trees

binary_trees

Binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Resources

Read or watch:

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;

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

Authors: