Skip to content

The study of a non-primitive non-linear data structures called binary trees and how they differ from non-primitive linear data structures like array, stacks, queues and linked list.

Notifications You must be signed in to change notification settings

SlamChillz/binary_trees

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

61 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

C - Binary trees

The learning objectives of this project are:

  • 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

Helper File

Header File

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

Data Structures

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;
typedef struct binary_tree_s bst_t;
typedef struct binary_tree_s avl_t;
typedef struct binary_tree_s heap_t;

Function Prototypes

File Prototype
binary_tree_print.c void binary_tree_print(const binary_tree_t *tree)
0-binary_tree_node.c binary_tree_t *binary_tree_node(binary_tree_t *parent, int value);
1-binary_tree_insert_left.c binary_tree_t *binary_tree_insert_left(binary_tree_t *parent, int value);
2-binary_tree_insert_right.c binary_tree_t *binary_tree_insert_right(binary_tree_t *parent, int value);
3-binary_tree_delete.c void binary_tree_delete(binary_tree_t *tree);
4-binary_tree_is_leaf.c int binary_tree_is_leaf(const binary_tree_t *node);
5-binary_tree_is_root.c int binary_tree_is_root(const binary_tree_t *node);
6-binary_tree_preorder.c void binary_tree_preorder(const binary_tree_t *tree, void (*func)(int));
7-binary_tree_inorder.c void binary_tree_inorder(const binary_tree_t *tree, void (*func)(int));
8-binary_tree_postorder.c void binary_tree_postorder(const binary_tree_t *tree, void (*func)(int));
9-binary_tree_height.c size_t binary_tree_height(const binary_tree_t *tree);
10-binary_tree_depth.c size_t binary_tree_depth(const binary_tree_t *tree);
11-binary_tree_size.c size_t binary_tree_size(const binary_tree_t *tree);
12-binary_tree_leaves.c size_t binary_tree_leaves(const binary_tree_t *tree);
13-binary_tree_nodes.c size_t binary_tree_nodes(const binary_tree_t *tree);
14-binary_tree_balance.c int binary_tree_balance(const binary_tree_t *tree);
15-binary_tree_is_full.c int binary_tree_is_full(const binary_tree_t *tree);
16-binary_tree_is_perfect.c int binary_tree_is_perfect(const binary_tree_t *tree);
17-binary_tree_sibling.c binary_tree_t *binary_tree_sibling(binary_tree_t *node);
18-binary_tree_uncle.c binary_tree_t *binary_tree_uncle(binary_tree_t *node);
100-binary_trees_ancestor.c binary_tree_t *binary_trees_ancestor(const binary_tree_t *first, const binary_tree_t *second);
101-binary_tree_levelorder.c void binary_tree_levelorder(const binary_tree_t *tree, void (*func)(int));
102-binary_tree_is_complete.c int binary_tree_is_complete(const binary_tree_t *tree);
103-binary_tree_rotate_left.c binary_tree_t *binary_tree_rotate_left(binary_tree_t *tree);
104-binary_tree_rotate_right.c binary_tree_t *binary_tree_rotate_right(binary_tree_t *tree);
110-binary_tree_is_bst.c int binary_tree_is_bst(const binary_tree_t *tree);
111-bst_insert.c bst_t *bst_insert(bst_t **tree, int value);
112-array_to_bst.c bst_t *array_to_bst(int *array, size_t size);
113-bst_search.c bst_t *bst_search(const bst_t *tree, int value);
114-bst_remove.c bst_t *bst_remove(bst_t *root, int value);
120-binary_tree_is_avl.c int binary_tree_is_avl(const binary_tree_t *tree);
121-avl_insert.c avl_t *avl_insert(avl_t **tree, int value);
122-array_to_avl.c avl_t *array_to_avl(int *array, size_t size);

Tasks

  • 0. New node

    • 0-binary_tree_node.c: C 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. Insert left

    • 1-binary_tree_insert: C 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. Insert right

    • 2-binary_tree_insert_right.c: C function that inserts 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. Delete

  • 4. Is leaf

    • 4-binary_tree_is_leaf.c: C function that checks if a given node is a leaf.
    • Returns 1 if the node is a leaf, 0 otherwise.
  • 5. Is root

    • 5-binary_tree_is_root.c: C function that checks if a given node is a root.
    • Returns 1 if the node is a root, 0 otherwise.
  • 6. Pre-order traversal

  • 7. In-order traversal

  • 8. Post-order traversal

  • 9. Height

  • 10. Depth

  • 11. Size

  • 12. Leaves

  • 13. Nodes

    • 13-binary_tree_nodes.c: C function that returns the number of nodes in a binary tree with at least one child.
  • 14. Balance factor

  • 15. Is full

  • 16. Is perfect

  • 17. Sibling

    • 17-binary_tree_sibling.c: C function that returns a pointer to the sibling of a given node in a binary tree.
    • Returns NULL if no sibling is found.
  • 18. Uncle

    • 18-binary_tree_uncle.c: C function that returns a pointer to the uncle of a given node in a binary tree.
    • Returns NULL if no uncle is found.
  • 19. Lowest common ancestor

    • 100-binary_trees_ancestor.c: C 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.
  • 20. Level-order traversal

  • 21. Is complete

  • 22. Rotate left

    • 103-binary_tree_rotate_left.c: C function that performs a left-rotation on a binary tree.
    • Returns a pointer to the new root node of the tree after rotation.
  • 23. Rotate right

    • 104-binary_tree_rotate_right.c: C function that performs a right-rotation on a binary tree.
    • Returns a pointer to the new root node of the tree after rotation.
  • 24. Is BST

    • 110-binary_tree_is_bst.c: C function that checks if a binary tree is a valid binary search tree.
    • Returns 1 if the tree is a valid BST, 0 otherwise.
  • 25. BST - Insert

    • 111-bst_insert.c: C 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.
  • 26. BST - Array to BST

    • 112-array_to_bst.c: C 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.
  • 27. BST - Search

    • 113-bst_search.c: C 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.
  • 28. BST - Remove

    • 114-bst_remove.c: C 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.
  • 29. Big O #BST

    • 115-O: Text 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.
  • 30. Is AVL

    • 120-binary_tree_is_avl.c: C 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.
  • 31. AVL - Insert

    • 121-avl_insert.c: C function that inserts a value in an AVL tree.
    • Returns a value to the inserted node, or NULL on failure.
  • 32. AVL - Array to AVL

    • 122-array_to_avl.c: C 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.
  • 35. Big O #AVL Tree

    • 125-O: Text file containing the average time complexities of AVL tree opeartions (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.
  • 41. Big O #Binary Heap

    • 135-O: Text file containing the average time complexities of binary heap opeartions (one answer per line):
      • Inserting the value n.
      • Extracting the root node.
      • Searching for a node in a binary heap of size n.

Author

About

The study of a non-primitive non-linear data structures called binary trees and how they differ from non-primitive linear data structures like array, stacks, queues and linked list.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages