0x1D C - Binary trees ✏️

C is a powerful general-purpose programming language. It can be used to develop software like operating systems, databases, compilers, and so on. This projects covers the concepts of binary trees! This was a project done with the contribution of my peer in many other SWE projects Jorge Zafra Kudos!

At the end of this project, We were able to undesrtand these questions:

  • 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

Tasks ✔️

  1. Function that creates a binary tree node
  2. Function that inserts a node as the left-child of another node
  3. Function that inserts a node as the right-child of another node
  4. Function that deletes an entire binary tree
  5. Function that checks if a node is a leaf
  6. Function that checks if a given node is a root
  7. Function that goes through a binary tree using pre-order traversal
  8. Function that goes through a binary tree using in-order traversal
  9. Function that goes through a binary tree using post-order traversal
  10. Function that measures the height of a binary tree
  11. Function that measures the depth of a node in a binary tree
  12. Function that measures the size of a binary tree
  13. Function that counts the leaves in a binary tree
  14. Function that counts the nodes with at least 1 child in a binary tree
  15. Function that measures the balance factor of a binary tree
  16. Function that checks if a binary tree is full
  17. Function that checks if a binary tree is perfect
  18. Function that finds the sibling of a node
  19. Function that finds the uncle of a node
  20. Function that finds the lowest common ancestor of two nodes
  21. Function that goes through a binary tree using level-order traversal
  22. Function that checks if a binary tree is complete
  23. Function that performs a left-rotation on a binary tree
  24. Function that performs a right-rotation on a binary tree
  25. Function that checks if a binary tree is a valid Binary Search Tree
  26. Function that inserts a value in a Binary Search Tree
  27. Function that builds a Binary Search Tree from an array
  28. Function that searches for a value in a Binary Search Tree
  29. Function that removes a node from a Binary Search Tree
  30. What are the average time complexities of those operations on a Binary Search Tree
  31. Function that checks if a binary tree is a valid AVL Tree
  32. Function that inserts a value in an AVL Tree
  33. Function that builds an AVL tree from an array
  34. Function that removes a node from an AVL tree
  35. Function that builds an AVL tree from an array
  36. What are the average time complexities of those operations on an AVL Tree
  37. Function that checks if a binary tree is a valid Max Binary Heap (Task in progress)
  38. Function that inserts a value in Max Binary Heap (Task in progress)
  39. Function that builds a Max Binary Heap tree from an array (Task in progress)
  40. Function that extracts the root node of a Max Binary Heap (Task in progress)
  41. Function that converts a Binary Max Heap to a sorted array of integers (Task in progress)
  42. What are the average time complexities of those operations on a Binary Heap

Results 📈

Filename
0-binary_tree_node.c
1-binary_tree_insert_left.c
2-binary_tree_insert_right.c
3-binary_tree_delete.c
4-binary_tree_is_leaf.c
5-binary_tree_is_root.c
6-binary_tree_preorder.c
7-binary_tree_inorder.c
8-binary_tree_postorder.c
9-binary_tree_height.c
10-binary_tree_depth.c
11-binary_tree_size.c
12-binary_tree_leaves.c
13-binary_tree_nodes.c
14-binary_tree_balance.c
15-binary_tree_is_full.c
16-binary_tree_is_perfect.c
17-binary_tree_sibling.c
18-binary_tree_uncle.c
100-binary_trees_ancestor.c
101-binary_tree_levelorder.c
102-binary_tree_is_complete.c
103-binary_tree_rotate_left.c
104-binary_tree_rotate_right.c
110-binary_tree_is_bst.c
111-bst_insert.c
112-array_to_bst.c
113-bst_search.c
114-bst_remove.c
115-O
120-binary_tree_is_avl.c
121-avl_insert.c
122-array_to_avl.c
123-avl_remove.c
124-sorted_array_to_avl.c
125-O
130-binary_tree_is_heap.c
131-heap_insert.c - Task pending
132-array_to_heap.c - Task pending
133-heap_extract.c - Task pending
134-heap_to_sorted_array.c - Task pending
135-O

Additional info 🚧

Resources

  • GLIBC 2.24
  • gcc 4.8.4
  • betty linter 0.32
  • Valgrind

Try It On Your Machine 💻

SORRY, DESPITE THE PROJECT IS FUNCTIONAL FOR EDUCATIONAL PURPOSES FOR YOU TO LEARN I AM NOT LEAVING IT AVAILABLE FOR TEST