4.2.7

Trees

Test yourself

Trees

Unlike other data structures in computer science, trees represent data hierarchically.

Illustrative background for Roots and branchesIllustrative background for Roots and branches ?? "content

Roots and branches

  • Trees begin with a ‘root’ node, with one or more ‘branches’ beneath it.
  • Each branch, in turn, can have one or more sub-branches connected to it.
Illustrative background for Tree constructionIllustrative background for Tree construction ?? "content

Tree construction

  • The rules for creating a tree are:
    • Each node must only be connected to one ‘parent’ node and one or more ‘children’.
    • There should be no connections directly between nodes on the same level of the hierarchy.
Illustrative background for Tree traversalIllustrative background for Tree traversal ?? "content

Tree traversal

  • There are three ways to navigate, or ‘traverse’ a tree data structure:
    • Pre-order.
    • In-order.
    • Post-order.
Illustrative background for Pre-order traversalIllustrative background for Pre-order traversal ?? "content

Pre-order traversal

  • Pre-order traversal starts with the root node, then visits each of the other nodes from left to right.
  • In the example shown, the nodes are visited in the following order:
    • Tiger, Zebra, Lion, Gazelle, Giraffe, Rhino, Hippo, Elephant
Illustrative background for In-order traversalIllustrative background for In-order traversal ?? "content

In-order traversal

  • In-order traversal starts with the nodes in the left subtree, then visits the root node followed by the nodes in the right subtree.
  • In this case, the nodes above are visited in the following order:
    • Lion, Zebra, Gazelle, Giraffe, Tiger, Elephant, Hippo, Rhino.
Illustrative background for Post-order traversalIllustrative background for Post-order traversal ?? "content

Post-order traversal

  • Post-order traversal starts by visiting the nodes in the left subtree from bottom to top, then the right subtree bottom to top, before finishing with a visit to the root node. - The nodes in the example above are therefore visited in the following order:
    • Lion, Gazelle, Giraffe, Zebra, Elephant, Hippo, Rhino, Tiger.

Jump to other topics

1Components of a Computer

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

5Legal, Moral, Cultural & Ethical Issues

6Elements of Computational Thinking

6.1Thinking Abstractly

6.2Thinking Ahead

6.3Thinking Procedurally

6.4Thinking Logically

6.5Thinking Concurrently

7Problem Solving & Programming

8Algorithms

Unlock your full potential with Seneca Premium

  • Unlimited access to 10,000+ open-ended exam questions

  • Mini-mock exams based on your study history

  • Unlock 800+ premium courses & e-books

Get started with Seneca Premium