Exploring Trees, Sorting, and Searching

What is a binary tree?

• A binary tree is a type of linked list.

• A binary tree is a data structure with no children.

• A binary tree is a data structure where each node has at most two children.

• A binary tree is a data structure where each node can have any number of children.

Explain the difference between a binary tree and a binary search tree.

• A binary tree is used for sorting data, while a binary search tree is used for storing data without any specific order.

• A binary tree has no specific ordering, while a binary search tree has a defined order based on node values.

• In a binary tree, all nodes must be leaf nodes, whereas in a binary search tree, all nodes must be internal nodes.

• A binary tree can only have two children, while a binary search tree can have multiple children.

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

• O(1)

• O(n log n)

• O(n)

• O(log n)

Describe the process of in-order traversal in a binary tree.

• Visits nodes in the order: current node, left subtree, right subtree.

• In-order traversal visits nodes in the order: left subtree, current node, right subtree.

• Visits nodes in the order: left subtree, right subtree, current node.

• Visits nodes in the order: right subtree, current node, left subtree.

What is the purpose of a heap in data structures?

• The purpose of a heap is to efficiently manage and retrieve the maximum or minimum element.

• To sort elements in ascending order.

• To store data in a linear fashion.

• To create a balanced binary tree.

List and explain two common sorting algorithms.

• Bubble Sort and Quick Sort

• Radix Sort and Shell Sort

• Heap Sort and Selection Sort

• Insertion Sort and Merge Sort

What is the worst-case time complexity of quicksort?

• O(n log n)

• O(n)

• O(log n)

• O(n^2)

How does merge sort work?

• Merge sort sorts an array by randomly shuffling its elements.

• Merge sort is a linear algorithm that processes elements one by one.

• Merge sort requires the entire array to be sorted before it can start merging.

• Merge sort is a divide-and-conquer algorithm that sorts an array by recursively splitting it into halves and merging the sorted halves.

What is the difference between linear search and binary search?

• Linear search is O(n) and works on unsorted lists; binary search is O(log n) and requires sorted lists.

• Linear search is faster than binary search.

• Linear search requires sorted lists to function.

• Binary search can be used on unsorted lists.

Explain the concept of tree height and its significance.

• Tree height is the longest path from the root to a leaf, impacting operation efficiency.

• Tree height refers to the width of the tree.

• Tree height is the total number of nodes in a tree.

• Tree height is the distance between any two leaves.