English National Curriculum:
Key Stage 2
Tooltip content
To use sequences, selection and repetition in programs.
learning objectives
Tooltip content
To understand and explain the features of trees (tree structures).
success criteria
- I can recognise a tree structure in everyday life.
- I can identify the features of a tree or tree structure.
top tips
- A tree stores data and is made up of nodes. There are different names for nodes in different parts of the tree structure.
- These trees are upside down, because their roots are at the top and leaves are at the bottom. Root nodes are also the only nodes not to have a parent node.
- A parent node is the node one step closer to the root node, than the node where you are currently located. A leaf is a node without a child. Siblings are two child nodes that share a parent.
Common misconceptions
- Trees and graphs are the same.
- Trees and graphs are different. Every node on a tree (except for the root) can only have 1 parent node, but the nodes on a graph can have more than 1 predecessor node (parent node).
Tree Structures
Tree Traversal
Depth-First Search
Breadth-First Search
A tree structure stores data and is made up of nodes. They are like upside down trees, because their root is at the top and their leaves are at the bottom.
Tree traversal is the process of updating or checking each node in a tree structure.
Depth-First Search involves searching the nodes of a tree structure vertically, traversing as far along a branch as possible before backtracking to the nearest parent node.
Breadth-First Search involves searching a tree structure horizontally, traversing all of the nodes at the same depth before moving onto the next row.
previous knowledge
A tree or tree structure is a hierarchical data structure that organizes data elements, called nodes, by connecting them with links, called branches.
These nodes are also given names to more easily identify their position when the tree is not visible. A root node is at the top of the tree. There is nothing above it. For example, you may have heard the term root directory before in computing, the top level directory in a file tree structure. Every node below the root that also contains branches beneath it is a parent node. These nodes hold their own information and information on the nodes beneath them. Any node without branches below is a leaf node. Children and Sibling nodes show relations of lower branch nodes to higher nodes. Sibling nodes share a common parent. Parent nodes have children nodes.
TOPIC BACKGROUND READING
Traversing a tree can become important when looking for single or multiple items or nodes within it. There are many ways to traverse a tree and some are more efficient than others.
The Depth-First-Search algorithm starts at the root of the tree and explored as far as possible along each branch before backtracking. This can be thought of as exploring the tree from top to bottom.
The Breadth-First-Search algorithm also starts at the root of the tree but unlike DFS, it explores the neighbor nodes first, before moving to the next-level neighbors. This can be thought of as exploring the tree from left to right.
