coderz.py

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