Binary tree search — AQA A-Level Computer Science

Q: What is the difference between searching an array with binary search and searching a BST?

Binary search on an array uses array indexing and arithmetic midpoints on fixed, contiguous memory. In contrast, searching a binary search tree traverses pointer references across dynamically allocated nodes in memory. While both share an average search time complexity of O(log n), a BST supports dynamic insertions and deletions without shifting elements in memory.

Q: Why is searching a binary search tree not always O(log n)?

The O(log n) efficiency depends directly on the tree height remaining proportional to log2(n). If keys are inserted in monotonic sorted order, each new node becomes a single right or left child. This results in an unbalanced, degenerate tree identical to a linked list with height n, causing the search complexity to become O(n).

Q: Can duplicate values be stored and searched in a standard binary search tree?

Standard binary search trees typically enforce unique keys. However, duplicates can be accommodated by defining a rule (for example, allowing keys less than or equal to the node value on the left branch) or by storing a counter/frequency variable inside each node.

Q: Is an iterative or recursive search better for binary search trees?

Both iterative and recursive approaches have the same time complexity. However, iterative search is generally more memory-efficient in practice because it uses O(1) auxiliary space, avoiding the call-stack overhead and risk of stack overflow associated with recursive calls on very deep trees.

A binary tree search is an efficient algorithm that navigates a binary search tree (BST) by comparing a target value against node keys to eliminate half the remaining subtrees at each step. In AQA A-Level Computer Science, searching an average balanced BST achieves O(log n) time complexity, whereas a degenerate linear tree degrades to O(n).

Binary tree search explained

A binary search tree stores items so that every node's left subtree holds smaller values and its right subtree holds larger values.

Read the full explanation

To search, the algorithm starts at the root, compares the target with the current node, and moves left or right accordingly until it finds the item or reaches a null pointer. Tracing means following this path step by step for a given target, recording each node visited and the comparison result at each step. Analysing time complexity means counting the number of nodes visited in the worst case. For a balanced tree with n nodes, the height is about log₂ n, so the search takes O(log n) time. For a degenerate tree where each node has only one child, the height becomes n, so the search takes O(n) time. Students must be able to show both the trace and the reasoning that links the height of the tree to the number of comparisons.

Your focus

Be able to trace and analyse the time complexity of the binary tree search algorithm.

Which command word is this?

Follow the execution of an algorithm step by step, showing all intermediate states, visited node values, and final return outputs.

Binary tree search exam tips

Topic Overview

Binary tree search is an essential non-linear search technique implemented on a binary search tree (BST). It relies on the fundamental structural invariant where every node to the left of a parent holds a lesser value, and every node to the right holds a greater value.

Understanding binary tree search is crucial for AQA A-Level Computer Science as it bridges dynamic abstract data types (ADTs) with algorithmic efficiency and Big-O notation. It directly connects tree traversal routines with real-world applications such as database indexing, compiler symbol tables, and associative memory lookups.

Key Concepts

→Binary Search Tree (BST) property: For any node n, all keys in n's left subtree are strictly less than n's key, and all keys in n's right subtree are strictly greater than n's key.
→Branch elimination: At each node, a single comparison discards the target from one half of the remaining subtree, yielding logarithmic height O(log n) when balanced.
→Tree degeneracy: When nodes are inserted in strictly ascending or descending order, the tree forms a single degenerate branch, increasing the search cost to linear time O(n).
→Pointer manipulation: Tree nodes typically contain data fields and memory pointers (left child and right child) which are dereferenced sequentially during search traversal.

Marking Points

Traces the search path from the root, comparing the target at each node and choosing left or right
Identifies the path length as the number of comparisons performed
States that a balanced tree of n nodes has height about log₂ n, giving O(log n) search time
Recognises that a degenerate tree with height n gives O(n) search time in the worst case

Examiner Tips

💡Write out the nodes visited in order when asked to trace a search, so each comparison is clear
💡Link time complexity to tree height explicitly in your answer
💡Consider both balanced and degenerate cases when analysing worst-case behaviour
💡When tracing tree searches, clearly list each node accessed in sequence rather than just writing the direction taken (e.g., write '45 -> 23 -> 34' instead of just 'Left, Right').
💡Be prepared to explain how tree re-balancing mechanisms (such as AVL or red-black trees) prevent the worst-case O(n) search complexity, even if you are not required to code them.

Common Mistakes

Assumes every binary search tree is balanced; correct it by checking how the tree was built, since inserting sorted data can produce a degenerate tree
Counts the number of nodes in the tree rather than the path length; correct it by counting only the nodes visited on the search path
Confuses binary search tree search with binary search on an array; correct it by explaining that the tree's structure, not array indexing, determines the path
Assuming binary search on an array is identical to searching a binary tree: While both achieve O(log n) average time, binary search on an array operates on static, contiguous memory using index arithmetic, whereas a BST search navigates dynamic pointers between heap-allocated nodes.
Believing that an in-order traversal performs a search: In-order traversal systematically visits every single node (O(n)) to output sorted data, whereas a binary tree search selectively branches down one path from root to leaf.

Revision Plan

1Day 1-2: Review tree terminology and practice drawing BSTs from various unordered and ordered data input sequences.
2Day 3-4: Write and trace recursive and iterative BST search algorithms by hand using standard AQA pseudocode.
3Day 5-6: Compare time complexity metrics (best, average, and worst-case) between balanced trees, degenerate trees, and sorted arrays.
4Day 7: Complete past-paper exam questions covering BST trace tables, diagram annotation, and pseudocode completion.

Exam Question Types

📋Tracing searches: Providing a tree diagram and asking for the sequence of nodes visited when searching for an existing or absent key.
📋Pseudocode implementation or completion: Writing a function to traverse and find a key, handling null pointer edge cases correctly.
📋Comparative analysis: Comparing the time and space complexity of searching a binary search tree versus a linear list or hash table.

Command Word Expectations (AQA)

Trace

Follow the execution of an algorithm step by step, showing all intermediate states, visited node values, and final return outputs.

Explain

Provide clear reasoning detailing how the BST search algorithm selects subtrees using inequalities, and how tree balance dictates algorithmic complexity.

Compare

Identify structural, algorithmic, and computational complexity similarities and differences between two search methods (e.g., binary search on an array vs BST search).

How Students Lose Marks (Examiner Pitfalls)

Pitfall: Confusing a general binary tree with a binary search tree (BST) when explaining search logic.

❌ Weak Answer (Loses Marks):You search a binary tree by looking at the root, and if it is not there, check both the left and right children until found.

Example improved answer:Compare the search key to the current node value. If equal, the search terminates successfully. If the search key is less than the current node value, recursively search the left subtree. If greater, recursively search the right subtree. If an empty pointer or null reference is reached, the item does not exist in the tree.

Examiner Tip: Always explicitly state the ordering property (left child < parent < right child) before describing the directional branching logic.

Pitfall: Assuming binary tree search is always O(log n) without considering tree balance.

❌ Weak Answer (Loses Marks):A binary search tree always takes O(log n) time because it halves the search space at every node.

Example improved answer:In a balanced binary search tree, the search time complexity is O(log n) because half of the remaining nodes are discarded at each comparison. However, in the worst-case scenario where items were inserted in sorted order, the tree degenerates into a linear linked list with a height of n, resulting in an O(n) search time complexity.

Examiner Tip: When asked for time complexity, specify both the average case for a balanced tree (O(log n)) and the worst case for an unbalanced or degenerate tree (O(n)).

Step-by-Step Worked Solutions

Question: A binary search tree stores the following integer keys inserted in this order: [45, 23, 67, 12, 34, 56, 89, 28]. Trace the steps required to search for the value 28, listing every node visited and stating whether the search was successful.

1.Step 1: Compare target (28) with root node (45). Since 28 < 45, branch left to node 23.
2.Step 2: Compare target (28) with current node (23). Since 28 > 23, branch right to node 34.
3.Step 3: Compare target (28) with current node (34). Since 28 < 34, branch left to node 28.
4.Step 4: Compare target (28) with current node (28). Values match (28 == 28). Terminate search.

Final Answer: Nodes visited in order: 45 -> 23 -> 34 -> 28. The search terminates successfully at node 28 after 4 comparisons.

Question: Write a recursive algorithm in pseudocode for a function `searchBST(node, target)` that returns True if target is present in the tree rooted at `node`, or False otherwise.

1.Step 1: Define base case 1: check if the node pointer is null/empty, returning False.
2.Step 2: Define base case 2: check if target matches current node value (`node.data == target`), returning True.
3.Step 3: Define recursive case 1: if `target < node.data`, return `searchBST(node.left, target)`.
4.Step 4: Define recursive case 2: if `target > node.data`, return `searchBST(node.right, target)`.

Final Answer: function searchBST(node, target) if node == null then return False else if node.data == target then return True else if target < node.data then return searchBST(node.left, target) else return searchBST(node.right, target) endif endfunction

Active Recall Memory Test

What is the time complexity of searching a balanced binary search tree containing n items?

Key Fact: O(log n)

Under what specific condition does a binary search tree degrade to a worst-case O(n) search time?

Key Fact: When items are inserted in already sorted order (strictly ascending or strictly descending), forming a linear degenerate tree.

Which node is inspected first during any standard binary tree search operation?

Key Fact: The root node.

What determines whether a search algorithm branches left or right at a given BST node?

Key Fact: Whether the search key is less than (branch left) or greater than (branch right) the key of the current node.

Frequently Asked Questions

What is the difference between searching an array with binary search and searching a BST?

Binary search on an array uses array indexing and arithmetic midpoints on fixed, contiguous memory. In contrast, searching a binary search tree traverses pointer references across dynamically allocated nodes in memory. While both share an average search time complexity of O(log n), a BST supports dynamic insertions and deletions without shifting elements in memory.

Why is searching a binary search tree not always O(log n)?

The O(log n) efficiency depends directly on the tree height remaining proportional to log2(n). If keys are inserted in monotonic sorted order, each new node becomes a single right or left child. This results in an unbalanced, degenerate tree identical to a linked list with height n, causing the search complexity to become O(n).

Can duplicate values be stored and searched in a standard binary search tree?

Standard binary search trees typically enforce unique keys. However, duplicates can be accommodated by defining a rule (for example, allowing keys less than or equal to the node value on the left branch) or by storing a counter/frequency variable inside each node.

Is an iterative or recursive search better for binary search trees?

Both iterative and recursive approaches have the same time complexity. However, iterative search is generally more memory-efficient in practice because it uses O(1) auxiliary space, avoiding the call-stack overhead and risk of stack overflow associated with recursive calls on very deep trees.

Binary tree search explained

Your focus

Which command word is this?

Binary tree search exam tips

More AQA A-Level Computer Science topics

Cookies on MasteryMind