Binary Tree

data-structures

Definition

Binary Tree

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

A binary tree is defined recursively: it is either empty (null) or consists of a root node and two disjoint binary trees called the left and right subtrees.

Visual Representation

Properties

For a binary tree with $n$ nodes and height $h$:

• The maximum number of nodes at level $l$ is $2^l$.
• The maximum number of nodes in a tree of height $h$ is $2^{h+1}-1$.
• The minimum height of a tree with $n$nodes is $\lfloor {\log }_{2}n\rfloor$.
• The maximum height of a tree with $n$nodes is $n-1$.

Complexity

The time complexity for most operations (search, insertion, deletion) in a binary tree is $O(h)$, where $h$ is the height. In a balanced tree,$h=O(\log n)$, whereas in a skewed tree,$h=O(n)$.