Binary tree

In computer science, a binary tree is a hierarchical tree data structure in which each node has at most two children, typically distinguished as the "left" child and the "right" child. It serves as a fundamental structure for implementing various abstract data types, including binary search trees and binary heaps, and is widely utilized in algorithms for searching, sorting, data compression, and expression evaluation.

Definition and Terminology

A binary tree is composed of nodes connected by edges. The terminology used to describe its components and metrics is standard across graph theory and computer science:

• Node: The fundamental unit of the tree, containing a value or data payload and references to its children.
• Root: The topmost node in the tree. A tree has exactly one root node, which has no parent.
• Leaf (External Node): A node with no children.
• Internal Node: A node with at least one child.
• Edge: The connection between a parent node and a child node.
• Depth: The depth of a node is the number of edges from the root to that node. The root node has a depth of 0.
• Height: The height of a node is the number of edges on the longest downward path between that node and a leaf. The height of the tree is the height of its root node.
• Subtree: A tree consisting of a node and all of its descendants. Every node in a binary tree defines a subtree.

Types of Binary Trees

Binary trees are categorized based on their structural properties and the arrangement of their nodes:

• Full Binary Tree: A tree in which every node has either zero or two children. No node has exactly one child.
• Perfect Binary Tree: A full binary tree in which all interior nodes have two children and all leaves have the same depth.
• Complete Binary Tree: A tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. This structure is highly efficient for array-based storage.
• Balanced Binary Tree: A tree where the height of the left and right subtrees of every node differs by at most a specific constant (usually 1). Examples include AVL trees and Red-Black trees, which guarantee logarithmic time complexity for operations.
• Degenerate (or Pathological) Tree: A tree where each parent node has only one associated child node. This structure effectively degrades into a linked list, resulting in linear time complexity for operations.

Mathematical Properties

Binary trees exhibit several fundamental mathematical properties related to their height, levels, and node counts (assuming the root is at level 0 and height $h$):

1. Maximum Nodes at Level $l$: The maximum number of nodes at any level $l$ is $2^l$.
2. Maximum Nodes in Tree: The maximum number of nodes in a binary tree of height $h$ is $2^{h+1} - 1$. This occurs in a perfect binary tree.
3. Minimum Height: For a binary tree with $N$ nodes, the minimum possible height is $\lfloor \log_2(N) \rfloor$.
4. Leaf and Internal Node Relationship: In a non-empty full binary tree, if $L$ is the number of leaf nodes and $I$ is the number of internal nodes with two children, then $L = I + 1$.

Storage and Representation

Binary trees can be represented in memory using two primary methods:

Linked Representation

The most common approach uses dynamically allocated nodes. Each node is a record (or object) containing the data element and two pointers (or references) to its left and right children. If a child does not exist, the corresponding pointer is set to null. This method is highly flexible and memory-efficient for sparse or unbalanced trees.

Array Representation

For complete binary trees, an implicit array-based representation is often used. The nodes are stored in a 1D array, and the relationships are determined by index arithmetic. Using 0-based indexing, for a node at index $i$:

• The left child is located at index $2i + 1$.
• The right child is located at index $2i + 2$.
• The parent is located at index $\lfloor (i - 1) / 2 \rfloor$.

This method avoids the memory overhead of pointers and improves cache locality, but it can waste significant space if the tree is not complete.

Traversal Methods

Traversing a binary tree involves visiting every node exactly once in a specific order. Traversal algorithms are broadly classified into depth-first and breadth-first strategies.

Depth-First Traversal

These methods explore as far down a branch as possible before backtracking. They are naturally implemented using recursion or a stack.

• Pre-order (Node, Left, Right): Visits the current node before its subtrees. Useful for creating a copy of the tree or generating prefix expressions.
• In-order (Left, Node, Right): Visits the left subtree, the current node, and then the right subtree. In a binary search tree, this yields the nodes in ascending sorted order.
• Post-order (Left, Right, Node): Visits the subtrees before the current node. Commonly used for deleting a tree or evaluating postfix mathematical expressions.

Breadth-First Traversal

• Level-order: Visits nodes level by level, from top to bottom and left to right. It is implemented using a queue and is useful for finding the shortest path or printing the tree level by level.

Applications

The binary tree is a versatile structure that forms the backbone of numerous advanced data structures and algorithms:

• Binary Search Trees (BST): Trees that maintain a sorted order, allowing for efficient $O(\log n)$ average-case searching, insertion, and deletion.
• Binary Heaps: Complete binary trees that satisfy the heap property (min-heap or max-heap). They are the underlying structure for priority queues and the heapsort algorithm.
• Expression Trees: Used in compilers and interpreters to represent the syntactic structure of mathematical or logical expressions, where leaves are operands and internal nodes are operators.
• Huffman Coding Trees: A specific type of binary tree used in the Huffman coding algorithm for lossless data compression, where characters are assigned variable-length prefix codes based on their frequencies.
• Decision Trees: Widely used in machine learning and data mining for classification and regression tasks, where internal nodes represent tests on attributes and leaves represent class labels.