Binary Tree Types

1. Full (Proper) Binary Tree

# Each nodes has either 2 or 0 children.

            12

    8               18

5       11

2. Degenerate (Pathological) Binary Tree

# Each internal node has either a right or a left child.
# Each node is a left node or each node is a right node.

        1       1
    2               2
3                       3

4. Complete Binary Tree

# Each level is filled from left to right.
            8

    5               3

4       6       7

5. Perfect Binary Tree

# Each internal node has 2 children and each leaf node is on the same level.
0               8
    
1       5               3

2   4       6       7       8
N = 2^(h+1) - 1 | height of root = 0

6. Balanced Binary Tree

# For each node, the difference in height between 
# the left and right subtrees is 1 or less.
            0

    1               2

3       4

7. Binary Search Tree (BST)

# Each node in the left subtree is less than the parent.
# Each node in the right subtree is greater than the parent.
# This rule applies to every node in the tree.

            8

    4               15

3       5       12      20

TreeNode Definition

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

GeeksForGeeks: Types of Binary Trees