Exploring Tree Data Structures

What is the time complexity of in-order traversal in a binary tree?

• O(n)

• O(log n)

• O(1)

• O(n^2)

Describe the process of a right rotation in an AVL tree.

• Right rotation involves swapping the root with its right child to create a new root.

• Right rotation is used to balance a right-heavy subtree by moving it to the left.

• Right rotation is a process that removes the left child of a node without restructuring the tree.

• Right rotation is a tree restructuring operation that balances an AVL tree by rotating a left-heavy subtree to the right.

What are the maximum and minimum number of children a B-tree node can have?

• Minimum: ⌈m/2⌉, Maximum: m

• Minimum: m/2, Maximum: 2m

• Minimum: 1, Maximum: m+1

• Minimum: m, Maximum: ⌊m/2⌋

Explain the difference between a max heap and a min heap.

• A max heap stores values in ascending order, while a min heap stores values in descending order.

• A max heap allows duplicate values, while a min heap does not.

• A max heap prioritizes the maximum value, while a min heap prioritizes the minimum value.

• A max heap is always a complete binary tree, while a min heap can be unbalanced.

How does a trie optimize search operations for strings?

• A trie compresses strings into a single node, eliminating the need for traversal.

• A trie sorts strings alphabetically, making binary search possible.

• A trie uses a hash table to store strings, allowing for faster lookups.

• A trie optimizes search operations by using a tree structure that allows for character-by-character traversal, reducing the number of comparisons needed.

What is the average time complexity for inserting an element into a binary search tree?

• O(1)

• O(n)

• O(n log n)

• O(log n)

What is the purpose of balancing an AVL tree after deletion?

• To maintain the height-balanced property of the tree.

• To reduce the overall height of the tree.

• To increase the number of nodes in the tree.

• To convert the tree into a binary search tree.

Describe the steps involved in deleting a node from a binary search tree.

• Find the node and replace it with its parent node.

• Delete the entire tree before removing the node.

• Locate the node, handle cases for leaf, one child, or two children, and perform the necessary deletions.

• Only remove the node if it has two children.

What is the height of a complete binary tree with n nodes?

• n/2

• log10(n)

• floor(log2(n))

• n-1

How do you perform a level-order traversal of a binary tree?

• Use a queue to traverse the tree level by level, processing each node from left to right.

• Traverse the tree in pre-order using a stack.

• Process all nodes in a single pass without a queue.

• Visit each node in reverse order using recursion.