Topic 5 - Abstract data structures [HL]

Binary trees

This section looks at how trees work logically, common terminology, how binary trees can be traversed to retrieve data in different ways and how trees can be sketched.

5.1.14-15 Characteristics of trees

Trees are hierarchical data structures that are best explained with a sketch.

Binary tree Figure 1: Binary tree

A tree consists of nodes, which contain a piece of information and are represented by numbers in this sketch. The uppermost node is called the root and it serves as the starting point when retrieving data from the tree - in Figure 1 the number 8 is the root node. It has therefore has the highest rank in the tree hierarchy. A node can link to other nodes, which are then called child nodes - in a binary tree to a maximum of two. Consequently, the upper node is called a parent node. For example, in the sketch number 3 is a parent node of 1 and 6, which are its child nodes. As 6 has further child nodes, it can be considered to be the root of a subtree, which is part of the tree as a whole. Number 1 on the other hand has no further child nodes, which is why it is called a leaf. Other leaves here are 4, 7 and 13.

Binary and non-binary trees

Binary trees have the characteristic of being ordered. The left-child (e.g. 3) must come before the parent node (i.e. 8) and the right-child must come after the parent node (i.e. 10). For this reason each node in a binary tree can have a maximum of two child nodes only.

Non-binary trees on the other hand do not follow these rules and could be used for example to represent animal species trees.

5.1.16 Different tree traversal methods

Preorder traversal

A walk in which each parent node is traversed before its children.

Preorder Tree Traversal Figure 4: Preorder Tree Traversal

  1. Display the data part of the root (or current node).
  2. Traverse the left subtree by recursively calling the pre-order function.
  3. Traverse the right subtree by recursively calling the pre-order function.

Result: F, B, A, D, C, E, G, I, H.

Inorder traversal

A walk in which a node’s left subtree, then the node itself, and finally its right subtree are traversed.

Inorder Tree Traversal Figure 2: Inorder Tree Traversal

  1. Traverse the left subtree by recursively calling the in-order function.
  2. Display the data part of the root (or current node).
  3. Traverse the right subtree by recursively calling the in-order function.

Result: A, B, C, D, E, F, G, H, I.

Postorder traversal

A walk in which the children are traversed before their respective parents are traversed.

Postorder Tree Traversal Figure 3: Postorder Tree Traversal

  1. Traverse the left subtree by recursively calling the post-order function.
  2. Traverse the right subtree by recursively calling the post-order function.
  3. Display the data part of the root (or current node).

Result: A, C, E, D, B, H, I, G, F.