Back to the full dot-point answer
SingaporeComputer ScienceQuick questions
Data Structures
Quick questions on Binary search trees explained: H2 Computing
6short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.
What is searching?Show answer
Searching mirrors binary search. Start at the root; if the target equals the node, you are done; if smaller, go left; if larger, go right; if you reach null, it is absent:
What is insertion?Show answer
Insertion follows the same path until it finds an empty (null) spot, then attaches the new node there:
What is in-order traversal gives sorted output?Show answer
An in-order traversal visits the left subtree, then the node, then the right subtree. Because left holds smaller keys and right holds larger, this always emits the keys in ascending order:
What is q1?Show answer
What does an in-order traversal of a binary search tree produce? [1 mark]
What is q2?Show answer
Inserting the keys 1, 2, 3, 4, 5 in that order into an empty BST gives what shape, and what search complexity? [2 marks]
What is q3?Show answer
Why is a balanced binary search tree preferred over an unbalanced one? [2 marks]
Have a question we have not covered?
This dot-point answer is short enough that we have not extracted many short questions yet. Read the full dot-point answer or ask Mo, our study assistant, in the chat for follow ups.