• A tree whose elements have at most 2 children is called a binary tree.
• Each element of a binary tree can have only 2 children, we name them the left and right child.

Height of the binary tree

• The height of a binary tree is equal to the largest number of edges from the root to the most distant leaf node.

Algorithm

begin height(root)
If node is NULL 
  then return 0
Else 
  If left child and right child nodes are NULL 
    return 1
Else 
  take two integers let 'l' and 'r' to store value of left child and right child recursively
  by using formula:
    height_of_a_tree = 1 + (which-one is bigger from 'l' & 'r')
 end height

Properties

• Time Complexity :
  • Worst case time : O(n)
• Space Complexity: O(n)

Number of Internal Nodes

• Internal Node is a node that can have at least one child (i.e. non-leaf node is an internal node).

Algorithm

begin internal_nodes( root )
If node is NULL 
  then return 0
If left child and right child nodes are NULL 
    return 0
Else 
    return 1 + internal_nodes( left child of node ) + internal_nodes( right child of node )

 end internal_nodes

Output

Number of internal nodes: 6.

100
  \
   120
      \
      130
         \
         140
            \
            150
              \
              160
                 \
                 170

Number of internal nodes: 3

                 100
              /       \
            30        150
         /    \      /      \
       20     50   122      188