There are various varieties of trees that are often used in the context of Data Structures and Algorithms (DSA). Here are a few of the most important:

##### Binary Tree:

- A binary tree is a type of tree data structure in which each node can only have two children.
- The left child is the left subtree, while the right child is the right subtree.
- Binary trees are commonly utilized as the foundation for more complicated tree topologies.

**Properties of a binary tree**:

- The maximum number of nodes at each level of i is 2 i.
- At height h, the maximum number of nodes possible is 2h+1 -1.
- At height h, the minimum number of nodes possible is equal to h+1.
- A minimum number of nodes will represent a tree with maximum height and vice versa.

**Time Complexity:**

Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
---|---|---|---|

Search | O(n) | O(1) | O(n) |

Insertion | O(n) | O(1) | O(n) |

Deletion | O(n) | O(1) | O(n) |

Finding Minimum/Maximum Value | O(n) | O(1) | O(n) |

Inorder Traversal | O(n) | O(n) | O(n) |

Preorder Traversal | O(n) | O(n) | O(n) |

Postorder Traversal | O(n) | O(n) | O(n) |

Height Calculation | O(n) | O(1) | O(n) |

**Space Complexity: O(n)**

##### Binary Search Tree (BST):

- A binary search tree is a binary tree in which the left child of a node has a value that is less than the node’s value and the right child has a value that is larger than the node’s value.
- This attribute allows for quick searching, insertion, and deletion operations, making it suitable for jobs like keeping a sorted collection of objects.

**Properties of Binary Search Tree:**

- BST maintains the order of its nodes.
- For any given node, all the values in its left subtree are less than its value, and all the values in its right subtree are greater than its value.
- Searching, insertion, and deletion operations can be performed efficiently in O(log n) time on average, where n is the number of nodes in the tree. However, in the worst case (a skewed tree), these operations can take O(n) time.

**Time Complexity:**

Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
---|---|---|---|

Search | O(n) | O(1) | O(log n) |

Insertion | O(n) | O(1) | O(log n) |

Deletion | O(n) | O(1) | O(log n) |

Finding Minimum/Maximum Value | O(n) | O(1) | O(log n) |

Inorder Traversal | O(n) | O(n) | O(n) |

Preorder Traversal | O(n) | O(n) | O(n) |

Postorder Traversal | O(n) | O(n) | O(n) |

Height Calculation | O(n) | O(1) | O(n) |

**Space Complexity: O(n)**

##### AVL Tree:

- A self-balancing binary search tree is an AVL tree.
- It differs from other forms of tree data structures in that it was the first tree to be dynamically balanced.
- A balancing factor is applied to each node in the AVL tree. This method is dependent on whether the tree is balanced.
- The balancing factor is a major property of the tree in the AVL Tree data structure.

**Balancing factor: **

- It is the difference between the left subtree and the right subtree.
- The value of a balancing factor must be 0, -1, or 1. Therefore, each node of an AVL tree should consist of a balancing factor value i.e. 0, -1, or 1.
- Balance Factor = (Height of Left Subtree – Height of Right Subtree)
- An AVL tree is said to be a balanced tree if the balance factor of each node is between -1 to 1.

Values of nodes other than -1, to 1 in an AVL tree will represent an unbalanced tree that needs to be balanced.

**If a node has a balance factor of 1**, it means that the left subtree is one level higher than the right subtree.**If a node has a balance factor of 0**, it means that the height of the left subtree and the right subtree is equal.**If a node has a balance factor of -1**, it means that the right subtree is one level higher than the left subtree or the left subtree is one level lower than the right subtree.

**Time Complexity:**

Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
---|---|---|---|

Search | O(log n) | O(1) | O(log n) |

Insertion | O(log n) | O(1) | O(log n) |

Deletion | O(log n) | O(1) | O(log n) |

Finding Minimum/Maximum Value | O(log n) | O(1) | O(log n) |

Inorder Traversal | O(n) | O(n) | O(n) |

Preorder Traversal | O(n) | O(n) | O(n) |

Postorder Traversal | O(n) | O(n) | O(n) |

Height Calculation | O(1) | O(1) | O(1) |

**Space Complexity: O(n)**

##### B-Tree:

- A B-tree is a self-balancing search tree optimized for disc or other direct-access storage systems.
- It can manage massive quantities of data since each node can have numerous keys and child pointers.
- B-trees are commonly used in file systems and databases because they allow for fast search, insertion, and deletion operations with a specified maximum height.
- They are designed to minimize disc I/O operations.

**Properties of a B-tree:**

- Keys are stored in increasing order for each node x.
- A Boolean value “x.leaf” exists in each node, which is true if x is a leaf.
- The internal nodes should have at most “n-1” keys, where n is the order of the tree. It should also have a pointer for each child.
- All the nodes will have at most n children and at least n/2 children, except the root node.
- The leaf nodes of the tree have the same depth.
- The root node will have a minimum of 1 key and at least two children.
- If n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2, h ≥ logt (n+1)/2.

**Time Complexity:**

Operation | Worst-Case Time Complexity | Best-Case Time Complexity | Average Time Complexity |
---|---|---|---|

Search | O(log n) | O(1) | O(log n) |

Insertion | O(log n) | O(1) | O(log n) |

Deletion | O(log n) | O(1) | O(log n) |

Finding Minimum/Maximum Value | O(log n) | O(1) | O(log n) |

Inorder Traversal | O(n) | O(n) | O(n) |

Preorder Traversal | O(n) | O(n) | O(n) |

Postorder Traversal | O(n) | O(n) | O(n) |

Height Calculation | O(1) | O(1) | O(1) |

**Space Complexity: O(n)**

*Note: also read about* DSA: Trees

**Follow Me**

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py

Staying up to the mark is what defines me. Hi all! I’m Rabecca Fatima a keen learner, great enthusiast, ready to take new challenges as stepping stones towards flying colors.

## Leave a Comment