9.2.1. Binary Tree Definition

A binary tree is a tree where we have a root and every node has 0, 1, or 2 children. So, binary trees in general can have arbitrary shapes.

A binary tree is a specific type of tree structure in computer science. It consists of nodes structured in a way that each node can have up to two children, which are referred to as the left and right children. The topmost node is called the root. Since nodes can have different numbers of children (0, 1, or 2), the overall shape of a binary tree can vary significantly; it can be balanced or skewed to one side.

Think of a binary tree like a family tree where each parent can have at most two children. Some families might have different numbers of children, so the structure of the family tree can look different based on how many children each parent has.

Binary trees can have very strange shapes, e.g., a root with 1 child or 2 children, or even skewed heavily to one side.

The shape of a binary tree does not need to be uniform or balanced; it can vary. For instance, a binary tree can be a straight line where each node has only one child on one side, which is called a skewed tree. This variability allows binary trees to represent a wide range of data structures effectively.

Imagine a branching road that starts straight but then bends heavily to one side due to land constraints. Just like the road, a binary tree can be straight at first but may turn in one direction based on how the 'data' (children) is organized.

A heap is a binary tree which has a very specific shape, where we fill up the tree nodes in a specific order.

Heaps are a specific type of binary tree that must follow two primary rules. First, they are filled from top to bottom and from left to right. This means that when adding nodes, you start with the root, then fill the left child, followed by the right child, continuing on each level until all nodes are filled. This strict procedure ensures that the shape of the heap remains consistent and predictable.

Consider stacking shelves in a grocery store. You always start filling the top shelf to the left and then move right before going down to the next shelf. This systematic way of stacking ensures that the shelves look organized and maximized for space.

The value property says that for every node, its value is greater than or equal to that of its children.

In heaps, each parent node must have a value that is at least equal to the values of its child nodes. This is known as the max heap property. For example, if a parent node has a value of 24, both its children must have values less than or equal to 24. This property must hold true for every node, ensuring that the largest element is always at the root of the heap.

Imagine a priority list where the most important task (highest value) must always be at the top. No matter what new tasks come in (children), they can only have lower or equal priority values compared to the top task. This ensures the most important task is always prioritized.

Examples of a heap with 4 and 7 nodes, and examples of structures that do not form valid heaps.

Valid heaps maintain both the correct structure (filled from top to bottom, left to right) and the max heap property. For example, a heap with 4 nodes where the root (24) is greater than both its children (11 and 7) satisfies both conditions. In contrast, a structure that leaves 'holes' (missing nodes) or one where a parent node is smaller than its child nodes would not be a valid heap.

Think of a pile of sorted boxes representing tasks. For them to be valid, each box must be placed in a specific spot (no empty gaps) and the heaviest items (most important tasks) should always be on the top for easy access. If boxes are missing or lighter items are above heavier ones, the organization fails.

--