Revise Trees and binary trees for IB Computer Science (5.3)

A tree is a collection of entities called nodes. Nodes are connected by edges. Each tree has exactly one root node, which is the starting point of the tree. Every other node is connected by a directed edge from exactly one other node, its parent. A node can have multiple child nodes. A path is a sequence of nodes and edges connecting a node with a descendant. For example, in a file system, the root directory (e.g., C:) is the root node, folders are nodes, and the files within them are also nodes. The connection between a folder and a sub-folder is an edge.

To analyse the efficiency of tree-based algorithms, we need to measure their structure. The depth of a node is the length of the path (number of edges) from the root to that node. The root node is at depth 0. The height of a tree is the depth of its deepest leaf node, which is equivalent to the length of the longest path from the root to any leaf. A tree with a single node has a height of 0. The level of a node is often defined as its depth, with the root being at level 0. Be careful, as some definitions start levels at 1, but the IB convention generally aligns with depth starting at 0.

While a general tree can have any number of children per node, a binary tree is a more restricted and very common type of tree. In a binary tree, each node can have at most two children. These children are distinguished as the left child and the right child. This ordering is important. A node with one child must specify whether it is a left or right child. This simple constraint makes binary trees much easier to implement and analyse, and they form the basis for many advanced structures, including the Binary Search Tree (BST) which we will cover separately.

For a binary tree of height $h$, the maximum number of nodes it can contain is $N_{max} = 2^{h+1} - 1$. This occurs when the tree is 'full', meaning every node has either 0 or 2 children, and all leaves are at the same depth.