**Trees**

Binary trees will be examined at the level of diagrams and descriptions. Students are not expected to construct tree algorithms using pseudocode.

Tracing and constructing algorithms are not expected.

5.1.14

Describe how trees operate logically (both binary and non-binary).

*Teaching Note:*

LINK Recursive thinking.

Sample Question - **FORMER CURRICULUM**:

(i) Briefly explain how a binary tree could be searched to check if a particular value

is stored in the tree. [3 marks]

JSR Notes:

As with lists, this will be gone over in much more detail in the OOP Option.

But in terms of * how trees operate logically*:

Both binary and non-binary trees are made of nodes containing both data, and also two links to two additional nodes. And access to the data in the tree is done by sequentially following along a certain path of those nodes.

In a **binary tree**, the data is organized such that data which is greater than a certain node is placed to the right of that node, and data which is lesser than a certain node is placed to the left of that node.

When *adding to a tree*, a piece of data moves down through the branches of the tree asking at each node whether it is greater or lesser than the node it is at. If it is greater than any given node it encounters when traveling down through the tree, it continues on to the right, and if it is lesser, it continues on to the left.

And conversely, when *searching through a tree* made in a binary way, the question is asked at each node "is what we are looking for greater or lesser than the node at which we presently are?". And if greater than, movement through the tree continues on the right branch, or if lesser, on the left branch.

In this way, searching is done in a log2, or binary, way. In a perfectly balanced tree, each step through it to find something eliminates half of the remaining elements in the search.