Consider you have two trees: a plain binary tree and a binary search tree (BST). Which reason best explains why BST is preferred for searching?
Think about how the order of elements affects the search speed.
A BST keeps elements in sorted order, so when searching, you can decide to go left or right subtree based on comparison, effectively skipping half the nodes each time. This makes search operations faster than in a plain binary tree where no order is guaranteed.
Given the following trees, what will be the output of searching for value 7?
Plain Binary Tree (no order): 1 -> 3 -> 5 -> 7 -> 9
BST (sorted): 5 -> 3 -> 7 -> 1 -> 9
Assume search returns True if found, False otherwise.
def search_plain(tree, value): # Simulate search by checking all nodes for node in tree: if node == value: return True return False def search_bst(tree, value): # Simulate BST search current = 0 while current < len(tree): if tree[current] == value: return True elif value < tree[current]: current = 2 * current + 1 # left child index else: current = 2 * current + 2 # right child index return False plain_tree = [1, 3, 5, 7, 9] bst_tree = [5, 3, 7, 1, 9] print(search_plain(plain_tree, 7)) print(search_bst(bst_tree, 7))
Check if 7 exists in both trees and how search works.
Both trees contain 7. The plain tree search checks all nodes and finds 7. The BST search navigates correctly to find 7 as well.
Consider these two search functions. One is for a plain binary tree, the other for a BST. Why does the plain binary tree search take longer?
def search_plain(tree, value):
for node in tree:
if node == value:
return True
return False
def search_bst(node, value):
if node is None:
return False
if node.value == value:
return True
elif value < node.value:
return search_bst(node.left, value)
else:
return search_bst(node.right, value)Think about how many nodes each search checks.
The plain tree search checks every node because it has no order to guide it. The BST search uses the order property to decide which subtree to search, skipping many nodes and thus faster.
After inserting values 10, 5, 15, 3, 7 into an empty tree, what is the printed in-order traversal of the BST and the plain binary tree (which inserts nodes sequentially to the right)?
class Node: def __init__(self, value): self.value = value self.left = None self.right = None def insert_bst(root, value): if root is None: return Node(value) if value < root.value: root.left = insert_bst(root.left, value) else: root.right = insert_bst(root.right, value) return root def inorder(root): return inorder(root.left) + [root.value] + inorder(root.right) if root else [] # Plain binary tree insertion sequentially to the right class PlainBinaryTree: def __init__(self): self.root = None def insert(self, value): new_node = Node(value) if not self.root: self.root = new_node return current = self.root while current.right: current = current.right current.right = new_node # Build BST bst_root = None for v in [10, 5, 15, 3, 7]: bst_root = insert_bst(bst_root, v) # Build Plain Binary Tree plain_tree = PlainBinaryTree() for v in [10, 5, 15, 3, 7]: plain_tree.insert(v) print(inorder(bst_root)) print(inorder(plain_tree.root))
In-order traversal of BST is sorted. Plain binary tree inserts sequentially to the right.
The BST in-order traversal prints sorted values: [3, 5, 7, 10, 15]. The plain binary tree inserts nodes sequentially to the right, so in-order traversal prints nodes in insertion order: [10, 5, 15, 3, 7].
Which explanation best describes why a BST usually performs better on average than a plain binary tree for search, insert, and delete operations?
Think about how order helps reduce the number of nodes checked.
BST uses the order property to decide which subtree to explore, effectively halving the search space each step, leading to average O(log n) time. Plain binary trees have no order, so operations may require checking many nodes, leading to O(n) time.