60 Questions
What is the definition of tree traversal?
Visiting each node of the tree exactly once
How many tree traversals are there for a tree with n nodes?
n! (n factorial)
In which traversal do you visit each level of the tree before moving on to the next level?
Breadth-first
What do most tree traversals provide?
A meaningful walkthrough of all elements
In which traversal do you visit the nodes from bottom to top and from right to left?
Bottom-up, right-left
What are the two general tree traversal classes?
Depth-first and Breadth-first
What does Depth-first traversal prioritize?
Visiting child nodes before sibling nodes
In height-first traversal, which task is performed first at each node?
Visiting a node (V)
Which traversal visits the nodes in the order: 1, 3, 4, 6, 7, 8, 10, 13, 14?
Inorder tree traversal
What is the correct order for postorder tree traversal of the given tree?
1 4 7 6 3 13 14 10 8
What is the correct order for preorder tree traversal of the given tree?
8 3 1 6 4 7 10 14 13
In pre-order traversal, what is the order of operations?
Visit (V), Left (L), Right (R)
In in-order traversal, when is the node visited in relation to its left and right children?
L is visited first, followed by V, and then R
In which traversal method does the visit operation happen before traversing the left and right children?
Pre-order
What is the first step in searching for a target value in a BST?
Compare target value with the element in the root node
In post-order traversal, what is the order of operations?
Left (L), Right (R), Visit (V)
What is the outcome if the subtree being searched is empty during a BST search?
The search is unsuccessful
What happens if the target value is greater than the element in the root node during a BST search?
Search the right subtree
What is the first step to insert a new element into a BST?
Search for the element in the BST
What should be done if the search for the new element in a BST leads to a null link?
Replace the null link by a link to a leaf node containing the new element
What is the outcome of the search if the new element is already present in the BST?
The search will lead to the existing element in the BST
In a BST, what determines whether the tree is well-balanced or ill-balanced?
The order of insertions
If the elements 16, 19, 23, 28, 42 are inserted in ascending order into a BST, what is the likely outcome?
The BST will be extremely ill-balanced
What is the likely balance outcome if the elements 42, 28, 23, 19, 16 are inserted into a BST?
The BST will probably be reasonably well-balanced
What is the process for removing a leaf node ( a node with 0 children ) in a BST?
Remove link to the node from parent
What is the process for removing a node with one child in a BST?
Replace node with child node
When deleting node 8 in a BST, what is the next smaller (inorder predecessor) to replace 8?
7
When deleting node 8 in a BST, what is the next larger (inorder successor) to replace 8?
10
When deleting a node with 2 children in a BST, how do you find the next smaller node to replace it?
Go left from the node to be removed, then keep going right until the right subtree is empty
What is the correct sequence of steps to find the next smaller value (inorder predecessor) when deleting a node in a BST?
Go left, then keep going right until reaching a null node
What condition must be maintained when replacing a node with 2 children in a BST?
All nodes in the left subtree are less than or equal to the node, and all nodes in the right subtree are greater
What impact can deletion have on a balanced BST?
Deletion can make a balanced BST ill-balanced
What is the worst-case time complexity for deletion in an ill-balanced BST?
O(n)
What is the best-case time complexity for deletion in a balanced BST?
O(log n)
What distinguishes a Heap from a Binary Search Tree (BST)?
Heaps are always a complete binary tree, while BST can be different shapes
What is the process for inserting a new node into a heap?
Add the new node to the lowest point in the tree and upheap its values
What characterizes a Max Heap?
The root is the largest element
In a max heap, when is a swap performed during insertion?
If the parent node is less than the new node
What is the defining characteristic of a Min Heap?
The root is the smallest element
What is the correct sequence of inserting the elements 8, 10, 3, 6, 7, 14, 1, 13, 4 into a min heap?
1, 3, 4, 6, 7, 14, 8, 13, 10
What is the process for removing a node from a heap?
Transfer the lowest, rightmost node to the root and downheap to rightful place
What is the restriction when deleting a node from a heap?
Only the root can be removed
What is the time complexity for any operation on a heap?
$O(\log n)$
What determines the swapping condition in a max heap during downheap?
If child node is greater than the new node
Which applications benefit from fast access to the smallest or largest element?
Applications requiring fast retrieval of specific elements
What type of data structure is a priority queue?
A structure that orders elements based on priority
What distinguishes a Heap from a Binary Search Tree (BST)?
Heaps are always complete binary trees, while BST can have different shapes
What is the defining characteristic of a Min Heap?
The root is the smallest element in the tree
In a max heap, when is a swap performed during insertion?
If the value of the new node is greater than its parent, swap the new node with its parent.
During deletion of a max heap, what is the condition to swap the parent node with a child node?
If the child node is greater than the parent node
When deleting from a min heap, what triggers a swap with the parent node?
If the child node is less than the new node
In a max heap, what is the condition to swap the parent node with a child node if both children are greater?
Swap with the larger child
What is the time complexity for any operation on a heap?
$O( ext{log } n)$
Which type of heap is great for applications requiring fast access to the smallest element?
Min heap
What is the minimum height possible for a complete heap?
The height is always minimum for the number of nodes
What is a defining characteristic of a complete heap?
It always has the minimum height possible for the number of nodes
What is the relationship between completeness and height in a heap?
Completeness ensures the minimum height for the number of nodes
What is the first step to build a max heap using the given data?
Start from the last non-leaf node and perform downheap operation
What is the outcome of extracting 2 values from the max heap?
The heap will be restructured to maintain the max heap property
What is the correct first step to repeat the process for a min heap?
Start from the last non-leaf node and perform downheap operation
Test your knowledge of tree traversal with this quiz. Explore the process of visiting each node of a tree and understand the different permutations and meaningful walkthroughs.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
