Binary tree is a rooted tree with following constraints:

• Every node can have at most two children. (zero, one and two)
• The two children of each node are called the left child and right child corresponding to their positions.
• A node can have only a left child or only a right child or it can have no children at all.

Terminologies used in Binary tree:

• Height of a node: As per the “Introduction to Algorithms” by Cormen et al., the height of a node X in a tree T is the number of edges on the longest downward simple path (number of edges) from X to a leaf.
• Height of a tree is defined as the height of its root node.
  We measure the height from bottom, so here height of node is like how much high a node is from the bottom (leaf node)
• Depth: the depth of a node Y is defined as the length of the simple path from the root node to X.
  We measure the depth from top, like depth of well look down from reference. Similarly, here reference is the root node for all the nodes and depth is how deep a node is from the root node.
  So, root is at depth zero.
  
  

  Fig. 1: Height, depth and level of B-tree

Properties of Binary Tree:

• In a binary tree with λ levels, the number of leaves L is:
  L≤2^λ-1
• In a binary tree the nuver of nodes n at level k, can be
  n≤ 2^k, for (k&ge0).
• In a binary tree with λ levels, the number of total nodes N is:
  N≤2^λ-1
• In a binary tree with N nodes, the number of levels λ is:
  λ≥⌈log(N + 1)⌉
• In a binary tree with L leaves, The the number of levels λ is:
  
  λ≥ ⌈log L⌉+ 1

Types of Binary tree

• Full Binary Tree: (sometimes proper binary tree or 2-tree or strictly binary tree) A Binary Tree is called full binary tree if every node has 0 or 2 children.
  Example:
  
  

  Fig. 2: Complete binary tree

  
  Properties of Full Binary tree:
  • If the number of leaf nodes are L and the number of internal nodes are I:
    L = I + 1
  • If the number of internal nodes is I, the total number of nodes N is:
    N = 2I + 1
  • If the total number of nodes is N, the number of internal nodes is I:
    I = (N – 1)/2
  • If, N is the total number of nodes, the number of leaves L will be:
    L = (N + 1)/2
    Or,
    N = 2L – 1
  • Complete Binary Tree: A Binary Tree is called Complete Binary Tree if all levels are completely filled (all internal nodes have two children) except possibly the last one and all nodes are as far left as possible.
    
    Example:
    
    

    Fig. 3: Complete binary tree

    
    Following examples of not a complete binary tree:
    
    

    Fig. 4: Examples of not complete binary tree

  • Perfect Binary Tree: It is a Binary in which all the internal nodes have exactly 2 children and all the leaf nodes are at same level.
    
    Example:
    
    

    Fig. 5: Perfect binary tree

  • Balanced Binary Tree: for each node, if the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1, holds true. In a balanced tree, the difference of the depth for any two leaves should be at most 1. AVL tree is an example of Balanced Binary tree.

    For implementation of Binary tree with C/C++ and JAVA, click here.

    Share this:

    • Click to share on Twitter (Opens in new window)
    • Click to share on Facebook (Opens in new window)

    Related