binarytree

A binary tree is a tree data structure in which each node has at most two children, commonly referred to as the left and right child. It is defined recursively: a binary tree is either empty or a node that contains data and two binary trees as its left and right subtrees.

Each node stores a value and references to its children. The top node is called the root. Substructures form subtrees, and properties such as height (the maximum distance from the root to a leaf), depth, size (the number of nodes), and balance describe the tree’s shape.

Variations include full binary trees (every node has 0 or 2 children), complete binary trees (all levels are fully filled except possibly the last, which is filled from left to right), and perfect binary trees (all internal nodes have two children and all leaves lie at the same depth). A binary search tree is a binary tree that maintains an ordered arrangement, enabling efficient search, insertion, and deletion. A binary heap is a complete binary tree that satisfies the heap property, used to implement priority queues.

Common operations for binary trees include insertion, deletion, and search (varies by tree type). Traversal methods such as in-order, pre-order, post-order, and level-order visit nodes in a defined sequence. In a binary search tree, average time for search, insertion, and deletion is O(log n), while in a degenerate or unbalanced tree it can degrade to O(n). Heaps support insert and extract-min or extract-max in O(log n).

Applications span data organization, coding and decoding schemes, expression evaluation, priority queues, and implementations of algorithms that rely on hierarchical partitioning. In programming, binary trees are commonly implemented with node objects containing value fields and left and right pointers or indices in an array-based representation.