Binary Tree Fundamentals

Binary trees are fundamental hierarchical data structures crucial in computer science for organizing and storing data efficiently. This topic explores their basic definitions, properties, common traversal methods, and introduces specialized binary tree variants like Binary Search Trees, AVL Trees, and Heaps. Understanding binary trees is key to mastering more complex data structures and algorithms.

1. What is a Binary Tree?

A binary tree, denoted as $T$ , is a hierarchical data structure defined recursively. It is either empty, or it consists of:

A special node called the root node.
Two distinct sets of nodes, $LT$ and $RT$ , known as the left subtree and right subtree of $T$ , respectively. Both $LT$ and $RT$ are themselves binary trees.

Crucially, the children of any node in a binary tree are ordered into a left child and a right child. A node can have:

Both a left and a right child.
Only a left child.
Only a right child.
No children (in which case it's a leaf node).

Here's a simple visual representation of a binary tree:

text

       A (Root)
      / \
     B   C
    /   / \
   D   E   F

Key Definitions:

Leaf Node: A node that has no children (no left child and no right child). In the example above, D, E, and F are leaf nodes.
Parent Node: A node with at least one child node. A is the parent of B and C. B is the parent of D. C is the parent of E and F.
Child Node: A node directly connected to another node (its parent) one level below it in the hierarchy. For example, B and C are children of A.
Level of a Node: The number of branches (edges) on the unique path from the root node to that specific node. The root is at level 0. Its children are at level 1, and so on.
- Level(A) = 0
- Level(B) = 1
- Level(D) = 2
Height of a Binary Tree: The maximum number of edges in a path from the root node to any leaf node. It can also be defined as the number of nodes on the longest path from the root to a leaf, minus one. For the tree above, the height is 2 (path A-B-D or A-C-E/F).

2. Binary Tree Traversal

Binary tree traversal refers to the process of visiting each node in the tree exactly once in a systematic way. There are three common methods, each defined by the order in which the root, left subtree, and right subtree are processed.

Consider the following binary tree for our examples:

text

       10
      /  \
     5    15
    / \     \
   3   7     20

2.1 Preorder Traversal (Root-Left-Right)

In Preorder traversal, the policy is to visit the Root node first, then recursively traverse its Left subtree, and finally recursively traverse its Right subtree.

Visit the root node of the current subtree.
Traverse the left subtree.
Traverse the right subtree.

For the example tree above, Preorder traversal would yield: $10 \rightarrow 5 \rightarrow 3 \rightarrow 7 \rightarrow 15 \rightarrow 20$

2.2 Inorder Traversal (Left-Root-Right)

In Inorder traversal, the policy is to recursively traverse the Left subtree first, then visit the Root node, and finally recursively traverse its Right subtree.

Traverse the left subtree.
Visit the root node of the current subtree.
Traverse the right subtree.

For the example tree above, Inorder traversal would yield: $3 \rightarrow 5 \rightarrow 7 \rightarrow 10 \rightarrow 15 \rightarrow 20$ Note: For a Binary Search Tree, Inorder traversal always produces elements in non-decreasing order.

2.3 Postorder Traversal (Left-Right-Root)

In Postorder traversal, the policy is to recursively traverse the Left subtree first, then recursively traverse its Right subtree, and finally visit the Root node.

Traverse the left subtree.
Traverse the right subtree.
Visit the root node of the current subtree.

For the example tree above, Postorder traversal would yield: $3 \rightarrow 7 \rightarrow 5 \rightarrow 20 \rightarrow 15 \rightarrow 10$

C++ Example: Node Structure and Traversal Functions

cpp

#include <iostream>
 
// Define a structure for a tree node
struct Node {
    int data;
    Node* left;
    Node* right;
 
    // Constructor to create a new node
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
 
// Function for Preorder Traversal (Root -> Left -> Right)
void preorderTraversal(Node* node) {
    if (node == nullptr) {
        return;
    }
    std::cout << node->data << " "; // 1. Visit root
    preorderTraversal(node->left);  // 2. Traverse left subtree

3. Binary Search Tree (BST)

A Binary Search Tree (BST) is a specialized type of binary tree that maintains a specific ordering property to facilitate efficient search, insertion, and deletion operations.

The key property of a BST is:

For any given node, all values in its left subtree are strictly less than the node’s value.
For any given node, all values in its right subtree are strictly greater than the node’s value.
Each node typically contains a unique key.

Here's an example of a BST:

text

       8
      / \
     3   10
    / \    \
   1   6    14
      /    /
     4    13

Operations on Binary Search Trees:

Common operations performed on BSTs include:

Checking if empty: Determines if the tree contains any nodes.
Search: To find a particular item.
- Start at the root node.
- If the target value matches the current node's value, the item is found.
- If the target value is lower than the current node's value, continue searching in the left subtree.
- If the target value is higher than the current node's value, continue searching in the right subtree.
- If the search reaches a null pointer (empty subtree), the item is not in the tree.
Insert: To add a new item while maintaining the BST property.
- Start at the root.
- Compare the new value with the current node's value: if lower, go left; if higher, go right.
- Continue this comparison and traversal until an empty (null) position is found.
- Insert the new node at that null position.
Delete: To remove an item. This operation is more complex as it needs to handle various cases (deleting a leaf node, a node with one child, or a node with two children) while preserving the BST property.

4. AVL Tree: A Self-Balancing BST

An AVL tree is a specialized type of Binary Search Tree that is self-balancing. This means it automatically adjusts its structure (through rotations) after insertions or deletions to maintain a roughly balanced height, ensuring that operations like search, insertion, and deletion remain efficient with $O(\log n)$ time complexity.

The defining characteristic of an AVL tree is its balance factor. For any node in an AVL tree, the difference between the height of its left subtree and the height of its right subtree cannot be more than one.

The Balance Factor (BF) for a node is calculated as: $BF = \text{height(left subtree)} - \text{height(right subtree)}$

For a tree to be considered balanced (an AVL tree), every node in the tree must satisfy the following condition: $-1 \le \text{Balance Factor} \le 1$

If the balance factor of any node falls outside this range (i.e., less than -1 or greater than 1), the tree is unbalanced at that node, and a series of rotations (single or double) are performed to restore the AVL property. An empty tree's height is typically considered -1.

Consider the example from the source (where 0, 1, 2 refer to node heights, and -1 an empty subtree):

text

Tree A (AVL)             Tree B (AVL)
       2 (BF=1-0=1)             2 (BF=1-0=1)
      / \                      / \
     1   0                    1   0
    / \                      / \
   0   0                    0   0
  / \                      / \
-1  -1                    -1  -1

In 'Tree A', the root node (height 2) has a left child (height 1) and a right child (height 0). The balance factor of the root is $1 - 0 = 1$ , which is within $[-1, 1]$ . All other nodes similarly satisfy the balance factor constraint, making it a valid AVL tree.

5. Heaps

A heap is a complete binary tree that satisfies the heap property. Unlike a Binary Search Tree, a heap does not maintain a sorted order across the entire tree, but rather a specific ordering relationship between parent and child nodes. There are two main types of heaps:

Min-Heap: For every node, its value is less than or equal to the values of its children. The smallest element is always at the root.
Max-Heap: For every node, its value is greater than or equal to the values of its children. The largest element is always at the root.

The source material implies a Min-Heap based on its examples ("The value in the root is the smallest of the tree", "Node value < child value").

A crucial characteristic of a heap is that it must be a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled, except possibly the last level, and all nodes in the last level are as far left as possible. This property makes heaps highly efficient for array-based implementations.

text

Example of a Min-Heap:
        1
       / \
      2   4
     / \ / \
    5  7 8 11

Operations on Heaps:

Insert an Item:
- Place the new item in the next available position at the bottom of the complete tree (as the leftmost available leaf) to maintain the complete tree property.
- Heapify-up (or percolate-up): Compare the newly inserted item with its parent. If the item violates the heap property (e.g., is smaller than its parent in a min-heap), swap them. Continue this process upwards (with the new item moving up the tree) until the item is at the root or is greater than or equal to its parent.
text
```
Example: Insert 1 into a heap
        2                2                1
       / \              / \              / \
      4   3            4   3            2   3
     / \              / \              / \
    5   7            5   7            4   7
   /                /                /
  1  (Add as leaf) 1  (Swap up)     5  (Swap up)
```
Remove an Item (Min element for Min-Heap):
- The item to be removed is always the root (minimum element in a min-heap).
- Replace the root's value with the value of the last item in the tree (the rightmost leaf at the deepest level).
- Remove the last item from its original position to maintain the complete tree property.
- Heapify-down (or percolate-down): Compare the new root with its children. If it violates the heap property (e.g., is larger than either child in a min-heap), swap it with the smaller of its two children. Continue this process downwards (with the new item moving down the tree) until the item is at a position where it satisfies the heap property relative to its children, or it becomes a leaf.
text
```
Example: Remove 1 from a heap
       1                  7                  2
      / \                / \                / \
     2   3              2   3              4   3
    / \ / \            / \ /              / \ /
   4  7 8 11          4  8 11           5  8 11
```

Implementing a Heap with an Array:

Because a heap is a complete binary tree, it can be efficiently represented using an array without explicit pointers for children, as the positions of children and parents can be calculated mathematically.

The root is at index $0$ .
For a node at index $i$ $i$ :
- Its left child is at index $2i + 1$ .
- Its right child is at index $2i + 2$ .
- Its parent is at index $\lfloor (i - 1) / 2 \rfloor$ .

This array-based representation simplifies memory management, improves cache performance due to contiguous memory allocation, and is widely used.

text

Tree:
        1
       / \
      2   4
     / \ / \
    5  7 8 11
 
Array Representation:
[ 1 | 2 | 4 | 5 | 7 | 8 | 11 ]
  0   1   2   3   4   5   6

Summary

Binary Trees are fundamental hierarchical data structures where each node has at most two children (left and right).
Key terminology includes root, leaf, parent, level, and height, which describe the structure and properties of the tree.
Tree Traversal methods (Preorder, Inorder, Postorder) provide systematic ways to visit all nodes, each with distinct ordering patterns used for different applications.
Binary Search Trees (BSTs) enforce an ordering property: left children are smaller, right children are larger, enabling efficient search, insertion, and ordered data retrieval.
AVL Trees are self-balancing BSTs that maintain a balance factor (difference in subtree heights) of at most 1 for all nodes, ensuring $O(\log n)$ performance for dynamic operations.
Heaps are complete binary trees that satisfy the heap property (e.g., min-heap: parent $\le$ children), useful for implementing priority queues and efficient min/max element retrieval, often implemented using arrays.

Assessed progress

Binary Tree Fundamentals

Binary Tree Fundamentals

1. What is a Binary Tree?

Key Definitions:

2. Binary Tree Traversal

2.1 Preorder Traversal (Root-Left-Right)

2.2 Inorder Traversal (Left-Root-Right)

2.3 Postorder Traversal (Left-Right-Root)

C++ Example: Node Structure and Traversal Functions

3. Binary Search Tree (BST)

Operations on Binary Search Trees:

4. AVL Tree: A Self-Balancing BST

5. Heaps

Operations on Heaps:

Implementing a Heap with an Array:

Summary

Key Concepts

Binary Tree

Tree Traversal

Binary Search Tree (BST)

AVL Tree

Heap

Quick Check

Advanced Data Structures

Advanced Data Structures