Binary tree - Types and Properties

Tree is sometimes binary tree (BT) and sometimes binary search tree(BST).
BT has maximum of 2 child nodes.
Binary Search Tree or Ordered tree(sometimes) is BT such that left child has value less than the parent and right child has value greater than parent.
Strictly binary tree - If every non-leaf node in BT has non empty left and right subtrees.
    A
   / \
  B   C
     /   \
    D    E
   / \
  F    G
Complete BT or Perfect BT of depth d is strictly BT all of whose leaves are at level d.
      A
   /    \
  B      C 
/   \   /    \
D   E  F   G
Almost complete BT (or sometimes complete BT) of depth d is BT such that :
1. Any node at level d-1 has 2 sons.
2. For any node in the tree with a right descendant at level d, nd must have a left son and every left descendant of node is either a leaf at level d or 2 sons.
i.e. it is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
These are note almost complete BT :
a) This has only 1 leave at leavel 1 2 3, violating condition 1.
         A
       /   \
      B     C
    /   \  

   D   E 

/   \  

F   G

b) This satisfies condition 1, since every leaf is either at level 2 or 3. But condition 2 is violated, because A has right descendant at level 3( J ) but also has left descendant (E ) which is a leaf at level 2.
        A
     /    \
    B      C 
   /   \   /    \
  D   E  F   G
/   \   /   \
H   I  J   K   

These are almost complete BT.
c) 

        A
     /    \
    B      C 
   /   \   /    \
  D   E  F   G
/   \  
H   I
d)
        A
     /    \
    B      C 
   /    \   /    \
  D    E  F   G
/   \  / 
H   I J

A degenerate tree is a tree where for each parent node, there is only one associated child node. This means that in a performance measurement, the tree will behave like a linked list data structure.

Properties of binary trees

• The number of nodes n in a perfect binary tree can be found using this formula: n = 2^{h + 1} − 1 where h is the height of the tree.
• The number of nodes n in a (almost) complete binary tree is minimum: n = 2^h and maximum: n = 2^{h + 1} − 1h is the height of the tree. where
• The number of nodes n in a perfect binary tree can also be found using this formula: n = 2L − 1 where L is the number of leaf nodes in the tree.
• The number of leaf nodes L in a perfect binary tree can be found using this formula: L = 2^h where h is the height of the tree.
• The number of NULL links in a Complete Binary Tree of n-node is (n+1).
• The number of leaf node in a Complete Binary Tree of n-node is UpperBound(n / 2).
• For any non-empty binary tree with n₀ leaf nodes and n₂ nodes of degree 2, n₀ = n₂ + 1.