Define Tree Traversal

1. Define Tree Traversal Tree traversal refers to the process of visiting all the nodes in a tree data structure, starting from the root. There are two main types of traversal:   Depth-First Traversal (DFS): Traverses as deep as possible before backtracking. o Preorder (Root, Left, Right) o Inorder (Left, Root, Right) o Postorder (Left, Right, Root) Breadth-First Traversal (BFS): Also known as level-order traversal, visits nodes level by level from left to right. 2. Define B-tree A B-tree is a self-balancing search tree in which nodes can have multiple children. It is typically used in databases and file systems for efficient storage and retrieval. A B-tree maintains sorted data and allows searches, insertions, deletions, and sequential access in logarithmic time.  Properties: o All leaf nodes are at the same level. o Nodes can have multiple children (up to m for a B-tree of order m). o Each node contains a certain number of keys and children pointers. 3. What are the different operations that can be performed on a heap? Common operations on a heap (usually implemented as a binary heap):       Insertion: Adds a new element while maintaining the heap property. Deletion: Typically removes the root (min for min-heap or max for max-heap) and restores the heap property. Heapify: Converts an array into a valid heap by adjusting the elements to maintain the heap property. Extract-Min/Extract-Max: Removes and returns the minimum or maximum element from a heap (depending on min-heap or max-heap). Peek: Retrieves the root without removing it. Decrease/Increase Key: Decreases or increases the key value of an element and reestablishes the heap property. 4. What are the different types of rotations used in an AVL tree? In an AVL tree, rotations are used to maintain balance after insertions and deletions. There are four types:     Right Rotation (LL Rotation): Performed when the left subtree is unbalanced (left-heavy). Left Rotation (RR Rotation): Performed when the right subtree is unbalanced (right-heavy). Left-Right Rotation (LR Rotation): Performed when the left child of a node is right-heavy. Right-Left Rotation (RL Rotation): Performed when the right child of a node is left-heavy. 5. What is the purpose of a self-balancing binary search tree? The purpose of a self-balancing binary search tree (BST) is to ensure that the height of the tree remains logarithmic with respect to the number of nodes, preventing it from degenerating into a linear structure like a linked list. This ensures efficient operations like search, insertion, and deletion, all of which can be performed in O(log n) time. 6. What is the purpose of a tree data structure? The purpose of a tree data structure is to represent hierarchical relationships between elements. Trees are used for:  Organizing data in a hierarchical manner (e.g., file systems, organizational charts).    Efficient searching and sorting (e.g., binary search trees, B-trees). Storing data for fast access and retrieval in applications like databases and compilers. Solving recursive problems through divide and conquer techniques. 7. Define a Binary Tree A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child. The binary tree structure is the basis for more specialized trees, such as binary search trees, AVL trees, and heaps. 8. What are the different operations that can be performed on a binary search tree (BST)? Common operations on a BST include:       Insertion: Insert a new node while maintaining the BST property (left < root < right). Deletion: Remove a node and restructure the tree to maintain the BST property. Search: Search for a node with a specific key. Traversal: Traverse the tree in different orders (inorder, preorder, postorder, etc.). Find Min/Max: Find the node with the minimum or maximum key. Successor/Predecessor: Find the in-order successor or predecessor of a given node. 9. What are the properties of an AVL tree? An AVL tree is a self-balancing binary search tree with the following properties:    The height difference between the left and right subtrees of any node (called the balance factor) must be between -1 and 1. Balance is maintained after every insertion or deletion using rotations. The time complexity for searching, insertion, and deletion is O(log n) due to its balanced nature. 10. What is double hashing in hashing? Double hashing is a technique used in open addressing to resolve collisions in a hash table. It uses a second hash function to calculate an additional probe distance when a collision occurs. The formula is typically: scss Copy code hash(key) = (hash1(key) + i * hash2(key)) % table_size Where hash1(key) is the primary hash function, hash2(key) is the secondary hash function, and i is the probe number. This method helps in reducing clustering and provides better performance for collision resolution. 4o