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:
Properties of a binary tree:
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)
Properties of Binary Search Tree:
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)
Balancing factor:
Values of nodes other than -1, to 1 in an AVL tree will represent an unbalanced tree that needs to be balanced.
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)
Properties of a B-tree:
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
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.
Factory Method is a creational design pattern that deals with the object creation. It separates…
You are given two singly linked lists that intersect at some node. Your task is…
A builder plans to construct N houses in a row, where each house can be…
Find the length of the longest absolute path to a file within the abstracted file…
You manage an e-commerce website and need to keep track of the last N order…
You are given a stream of elements that is too large to fit into memory.…