1. Introduction to Binary Tree

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. It is one of the most fundamental and widely used structures in computer science.

Binary Tree Terminology:

• Root: The topmost node in a tree.
• Node: A point in the tree that contains data and possibly pointers to child nodes.
• Edge: The link between a parent and a child node.
• Leaf: A node that has no children (both left and right are null).
• Parent: A node that has one or more children.
• Depth: The length of the path from the root to a node.
• Height: The length of the path from a node to its deepest descendant.

Properties of Binary Trees:

• A binary tree can be empty or contain a single node (the root).
• The maximum number of nodes at level L of a binary tree is \( 2^L \).
• A binary tree with height h has at most \( 2^{h+1} - 1 \) nodes.

2. Types of Binary Trees

1. Full Binary Tree: Every node has either 0 or 2 children.
2. Complete Binary Tree: All levels are completely filled except possibly the last, which is filled from left to right.
3. Perfect Binary Tree: All internal nodes have two children, and all leaf nodes are at the same level.
4. Balanced Binary Tree: The difference in height between the left and right subtree of any node is at most 1.