‹ Back to the paper
Question 2(a)
2 marks
Computer ScienceISC 2020 Computer Science Paper 1DifferentiateData structures
Differentiate between the following.
State the difference between a Binary Tree structure and a single Linked List.
Answer
Answer
Binary tree: a non-linear, hierarchical data structure with a root; every node can have up to two children (left and right), so each node holds two links. Data is reached by moving down from the root through a path, and in a binary search tree searching is fast (about $O(\log n)$ for a balanced tree).
Single linked list: a linear data structure; each node holds one link (next) to the following node, so the nodes form a single chain from the first node to the last. Elements can be reached only sequentially, so searching takes $O(n)$.