Types of Binary Trees

Types of Binary Trees:

1. Full Binary Tree:
   • Every node in a full binary tree has either 0 or 2 children.
   • There are no nodes with only one child.

2. Perfect Binary Tree:
   • A perfect binary tree is a full binary tree in which all leaf nodes are at the same level.
   • The number of nodes at each level is maximized, and the tree is balanced.

3. Complete Binary Tree:
   • A complete binary tree is a binary tree in which all levels, except possibly the last level, are completely filled.
   • If the last level is not complete, the nodes are filled from left to right.

4. Balanced Binary Tree:
   • A balanced binary tree is a binary tree in which the heights of the left and right subtrees of any node differ by at most one.
   • Examples of balanced binary trees include AVL trees and Red-Black trees.

5. Binary Search Tree (BST):
   • A binary search tree is a binary tree with the following properties:
     • The left subtree of a node contains only nodes with keys less than the node's key.
     • The right subtree of a node contains only nodes with keys greater than the node's key.
     • The left and right subtrees must also be binary search trees.

6. Degenerate (or Pathological or Skewed) Tree:
   • Each parent node has only one child, making it essentially a linked list.