From Roots to Leaves: Trees P2🌲

Release .9

In DSA, trees support a range of operations which varies depending upon the type of tree.
The Most common operations are discussed here :

• Insertion: Adding a new node to the tree.

• Deletion: Removing a node from the tree.

• Search: Finding a specific node with a given value in the tree.

• Traversal:

  1. Inorder Traversal: Visiting nodes in a specific order (typically left, root, right).
  2. Preorder Traversal: Visiting nodes in a specific order (typically root, left, right).
  3. Postorder Traversal: Visiting nodes in a specific order (typically left, right, root).

• Minimum and Maximum: Finding the node with the minimum or maximum value in a tree.

• Successor and Predecessor: Finding the node with the next larger or smaller value, respectively, with respect to the given node.

• Height and Depth: Calculating the height (the length of the longest path from the root to a leaf) and depth of a tree or a specific node.

• Balancing: Balancing operations for self-balancing trees like AVL trees and Red-Black trees to maintain their balance properties.

• Counting Nodes: Counting the number of nodes in the tree, including all nodes or specific subsets (e.g., leaf nodes).

• Checking Properties: Verifying that the tree satisfies certain properties, such as being a binary search tree or a balanced tree.

• Modification: Changing the value or properties of a node within the tree.

• Tree Construction: Building a tree from various sources, such as arrays, lists, or other data structures.

• Conversion: Converting between different types of trees or tree representations.

• Serialization and Deserialization: Converting a tree into a serialized format for storage or transmission and then reconstructing the tree from the serialized data.

• LCA (Lowest Common Ancestor): Finding the lowest common ancestor of two nodes in a tree.

• Level Order Traversal: Visiting nodes level by level, starting from the root.

Binary Search Trees:

• It is a type of binary tree.
• All nodes of the left subtree are lesser than the node itself.
• All nodes of the right subtree are greater than the node itself. Left and Right subtrees are also binary trees.
• There are no duplicate nodes.

This below is an example of a Binary Search Tree:

1. Insertion: To insert a new element into a BST, you start at the root and traverse the tree, comparing the element's value with the values of nodes. Insert the new element as a leaf node where it satisfies the BST properties.

2. Deletion: Deleting a node in a BST can be a bit more complex. You have to consider different cases:

3. If the node has no children, simply remove it.

4. If the node has one child, replace it with its child.

5. If the node has two children, find the in-order predecessor or successor (node with the maximum value in the left subtree or the minimum value in the right subtree) and replace the node with it.

6. Search: To search for an element in a BST, start at the root and traverse the tree based on comparisons. You can quickly find the desired element in O(h) time, where h is the height of the tree.

7. In-order Traversal: This operation visits all the nodes in a BST in ascending order, which is useful for sorting the elements stored in the tree.

AVL Tree:
An AVL Tree (Adelson-Velsky and Landis Tree) is a self-balancing binary search tree with an additional property:
For any node in the tree, the heights of its left and right subtrees differ by at most 1.

Example:

Operations on AVL Tree:

1. Insertion: When you insert a new element, you follow the same procedure as in a regular BST. After insertion, you check the balance factor (the difference in heights of the left and right subtrees) of each node on the path from the newly inserted node to the root. If it becomes unbalanced, you perform rotations to maintain the AVL property.

2. Deletion: Similar to insertion, you delete the node following regular BST deletion rules. After deletion, you need to check and rebalance the tree, just like in the insertion operation.

3. Search: Searching in an AVL tree is the same as in a regular BST and is efficient with a time complexity of O(log n).

4. In-order Traversal: Just like in a regular BST, an in-order traversal of an AVL tree gives you a sorted list of elements.

5. Rotations in AVL Trees:
   There are four types of rotations in AVL trees to restore balance:

• Left-Left (LL) Rotation: Occurs when a node is unbalanced with its left child, and the left child is also unbalanced with its left child.

• Right-Right (RR) Rotation: Occurs when a node is unbalanced with its right child, and the right child is also unbalanced with its right child.

• Left-Right (LR) Rotation: Occurs when a node is unbalanced with its left child, and the left child is unbalanced with its right child.

• Right-Left (RL) Rotation: Occurs when a node is unbalanced with its right child, and the right child is unbalanced with its left child.

AVL trees maintain their balance through these rotations even after multiple insertions and deletions.
This guarantees efficient O(log n) time complexity for various operations, making AVL trees an excellent choice for applications that require fast searching and sorting.

I hope this post was informative and helpful.
If you have any questions, please feel free to leave a comment below.

Happy Coding 👍🏻!
Thank You