Prashnikaप्रश्निका
Code
About
‹ 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.

Open in the Binary tree and BST tool

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)$.