Exploring Trees and Linked Lists

What is the purpose of rotations in an AVL tree?

• To increase the height of the tree.

• To maintain balance in the tree.

• To convert the tree into a binary search tree.

• To reduce the number of nodes in the tree.

Describe the properties that define a Red Black tree.

• Every node must have two children.

• All nodes must be black.

• The root can be red.

• A Red Black tree is defined by the following properties: 1. Each node is red or black. 2. The root is black. 3. Red nodes cannot have red children. 4. Every path from a node to its descendant null nodes has the same number of black nodes. 5. New nodes are inserted as red.

What are the different methods of traversing a binary search tree?

• In-order, Pre-order, Post-order, Level-order

• Top-down, Bottom-up, Side-order

• Sequential, Circular, Diagonal

• Depth-first, Breadth-first, Random-order

List the basic operations that can be performed on a linked list.

• Reversing

• The basic operations on a linked list are: 1. Insertion 2. Deletion 3. Searching 4. Traversal

• Merging

• Sorting

Compare the efficiency of AVL trees and Red Black trees in terms of balancing.

• Red-Black trees are always more balanced than AVL trees.

• Red-Black trees require more rotations to maintain balance than AVL trees.

• AVL trees have faster updates and slower lookups than Red-Black trees.

• AVL trees provide stricter balancing than Red-Black trees, leading to faster lookups but slower updates.

What are some common applications of linked lists in programming?

• Implementing binary trees

• File I/O operations

• Common applications of linked lists include implementing stacks and queues, dynamic memory allocation, adjacency lists for graph representation, maintaining a list of items in a specific order, and undo functionality in applications.

• Sorting algorithms

Explain the different types of tree traversals and their use cases.

• In-order, Out-order, Back-order, Forward-order

• Depth-first, Breadth-first, Random-order, Circular-order

• The different types of tree traversals are Pre-order, In-order, Post-order, and Level-order.

• Pre-order, Post-order, Side-order, Diagonal-order

How do you create an AVL tree from a given set of values?

• Insert values into an empty AVL tree, perform rotations to maintain balance.

• Sort the values before inserting them into the AVL tree

• Remove values from the AVL tree to create balance

• Insert values into a binary search tree without balancing

What is the representation of a binary tree in memory?

• A binary tree is represented using a matrix format.

• A binary tree is stored as a linked list of nodes.

• A binary tree is represented in memory using nodes with pointers to left and right children.

• A binary tree is represented as a single array without pointers.

What is the time complexity of searching in a binary search tree?

• O(n log n) in the average case.

• O(log n) on average, O(n) in the worst case.

• O(n) on average, O(log n) in the worst case.

• O(1) for all cases.