Here is the detailed explanation of Binary Trees and its Types

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

• The structure of a binary tree is such that each node can have zero, one, or two children.

• The topmost node in a binary tree is called the root, and nodes with no children are called leaves.

• A binary tree is **proper **if each node has either zero or two children.

**Types of Binary Tree:**

**Types of Binary Tree based on the number of children:**

Binary trees are categorized based on the number of children each node can have. The main types of binary trees based on the number of children are:

**Full Binary Tree (Proper Binary Tree):**

- In a full binary tree, every node has either zero or two children.
- Every internal node (non-leaf node) has exactly two children.
- All leaves are at the same level.
- Example:

```
1
/ \
2 3
/ \ / \
4 5 6 7
```

**Degenerate (or Pathological) Binary Tree:**

- In a degenerate binary tree, each parent node has only one associated child node.
- It essentially behaves like a linked list data structure.
- It has a time complexity similar to linked lists for many operations.
- Example:

```
1
\
2
\
3
\
4
\
5
```

**Skewed Binary Tree**:

- A skewed binary tree is a type of degenerate binary tree where all nodes have one child except one.
- Can be either left-skewed or right-skewed depending on whether all nodes are leaning towards the left or right respectively.
- Example:

Here’s an example of a left-skewed binary tree:

```
1
/
2
/
3
/
4
```

here’s an example of a right-skewed binary tree:

```
1
\
2
\
3
\
4
```

**Types of Binary Tree On the basis of the completion of levels:**

**Complete Binary Tree**:

- In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes are as left as possible.
- In other words, a complete binary tree is just like a full binary tree, but with the last level filled from left to right.
- It allows for efficient storage and representation.
- Examples:

```
1
/ \
2 3
/ \ / \
4 5 6 7
```

**Perfect Binary Tree**:

- In a perfect binary tree, all internal nodes have exactly two children, and all leaf nodes are at the same level.
- Every level of the tree is completely filled.
- Examples:

```
1
/ \
2 3
/ \ / \
4 5 6 7
```

**Balanced Binary Tree**:

- A balanced binary tree is a binary tree in which the height of the two subtrees of any node never differs by more than one.
- These trees optimize search and insertion operations.
- Examples:

```
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
```