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 nodes and height :

• The maximum number of nodes at level is .
• The maximum number of nodes in a tree of height is .
• The minimum height of a tree with nodes is .
• The maximum height of a tree with nodes is .

Complexity

The time complexity for most operations (search, insertion, deletion) in a binary tree is , where is the height. In a balanced tree,, whereas in a skewed tree,.