# Types of binary tree

## Types of binary tree

##### Full Binary Tree

A binary tree is full if each node has 0 or 2 children. We can also say that a full binary tree is a binary tree in which all the nodes, except the leaves, have two children.

Here are examples of full binary trees. ##### Complete binary tree

A binary tree is complete if all the levels are completely filled, except maybe the last level and the last level has all the keys as left as possible. ##### Perfect binary tree

A binary tree is perfect if all the internal nodes have two children and all the leaves are on the same level.

A perfect binary tree of height h a $$2^h - 1$$ node. ##### Balanced binary tree

A binary tree is balanced if its height is $$O(log n)$$, where n is the number of nodes.

•   AVL trees maintains the height in $$O(log n)$$ while ensuring that the difference between the heights of the left and right subtrees is 1.
•   The red-black trees maintain the height in $$O(log n)$$ ensuring that the number of black nodes on each root-to-leaf path is the same and that there are no adjacent red nodes. Binary balanced search trees are good from a performance point of view because they provide $$O(log n)$$ time for searching, inserting and deleting. 