Thread Academy

Tree Structures

Organise hierarchical data with binary trees and traversals.

  • Define and explain Tree Structures in your own words
  • Use key terms such as node accurately
  • Apply what you have learned to new examples and questions
  • Avoid the common mistakes learners make with this topic

This lesson focuses on Tree Structures: organise hierarchical data with binary trees and traversals.

Definition: Tree Structures

Organise hierarchical data with binary trees and traversals.

Key ideas

Trees turn searching into halving

A binary search tree keeps smaller values left and larger values right, so each comparison discards half the tree — the same idea as binary search, built into the structure. Traversals visit nodes in different orders: in-order on a binary search tree yields the values sorted. Insert order shapes the tree, and a badly ordered insert degrades it into a slow linked list.

Graphs model the real world

Roads, friendships, computer networks and dependencies are all graphs: nodes for places or things, edges for connections. Weighted edges let algorithms such as Dijkstra's find the cheapest route. Unlike trees, graphs can contain cycles — paths that loop back — which algorithms must handle to avoid going round forever.

Key term — node: A single element in a tree or graph, holding data plus links to other nodes.

Worked example: Tree Structures

What does an in-order traversal of a binary search tree produce?

The values in ascending sorted order.

Answer: The values in ascending sorted order.

Common mistakes
  • Popping or dequeuing from an empty structure Correction: always check the structure is not empty first — removing from nothing causes an underflow error.
  • Using a stack where a queue is needed Correction: ask 'must the first arrival be served first?' — if yes, you need a queue; a stack would serve the last arrival first.

Practice

Insert 5, 3, 8, 1 into an empty binary search tree in that order. What is the root's left child?
Smaller values go left of each node.

3 — it goes left of root 5, and then 1 goes left of 3.

Which structure models a web browser's back button: stack or queue? Why?
The last page visited is the first you go back to.

A stack — each new page is pushed, and Back pops the most recent page, which is last-in, first-out.

A queue holds [A, B, C] with A at the front. After one dequeue and one enqueue of D, what is the queue?
Dequeue removes from the front; enqueue adds at the rear.

[B, C, D] — A leaves from the front and D joins at the rear.

In a road network modelled as a graph, what do nodes, edges and weights represent?
Think about junctions, roads and distances.

Nodes are junctions (or towns), edges are the roads between them, and weights are distances or travel times.

Quick check

Tree Structures — quick check

Which of these best defines "node"?

A single element in a tree or graph, holding data plus links to other nodes.

True or false: a stack can be used to check whether brackets in an expression are balanced.

True — push each opening bracket and pop on each closing one; the last opened must be the first closed, which is exactly LIFO.
Key takeaways
  • Tree Structures: organise hierarchical data with binary trees and traversals.
  • Trees turn searching into halving: A binary search tree keeps smaller values left and larger values right, so each comparison discards half the tree — the same idea as binary search, built into the structure.
  • stack: A last-in, first-out structure: items are added and removed from the same end, called the top — like a spring-loaded plate dispenser.
  • Watch out for: popping or dequeuing from an empty structure
← Using QueuesGraph Networks →Back to Grade 11 chaptersRelated resources →