Data Structure & Algorithm in Java

⌘K
  1. Home
  2. Docs
  3. Data Structure & Alg...
  4. Trees
  5. Binary Trees and its Types

Binary Trees and its Types

Here is the detailed explanation of Binary Trees and its Types

Types of Binary Tree based on the number of children:

Binary trees are categorized based on the number of children each node can have. The main types of binary trees based on the number of children are:

  • In a full binary tree, every node has either zero or two children.
  • Every internal node (non-leaf node) has exactly two children.
  • All leaves are at the same level.
  • Example:
      1
    /   \
   2     3
  / \   / \
 4   5 6   7
    
  • In a degenerate binary tree, each parent node has only one associated child node.
  • It essentially behaves like a linked list data structure.
  • It has a time complexity similar to linked lists for many operations.
  • Example:
 1
  \
   2
    \
     3
      \
       4
        \
         5
  • A skewed binary tree is a type of degenerate binary tree where all nodes have one child except one.
  • Can be either left-skewed or right-skewed depending on whether all nodes are leaning towards the left or right respectively.
  • Example:

Here’s an example of a left-skewed binary tree:

         1
       /
      2
     /
    3
   /
  4

here’s an example of a right-skewed binary tree:

1
 \
  2
   \
    3
     \
      4

Types of Binary Tree On the basis of the completion of levels:

  • In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes are as left as possible.
  • In other words, a complete binary tree is just like a full binary tree, but with the last level filled from left to right.
  • It allows for efficient storage and representation.
  • Examples:
      1
    /   \
   2     3
  / \   / \
 4   5 6   7
  • In a perfect binary tree, all internal nodes have exactly two children, and all leaf nodes are at the same level.
  • Every level of the tree is completely filled.
  • Examples:
      1
    /   \
   2     3
  / \   / \
 4   5 6   7
  • A balanced binary tree is a binary tree in which the height of the two subtrees of any node never differs by more than one.
  • These trees optimize search and insertion operations.
  • Examples:
       1
     /   \
    2     3
   / \   / \
  4   5 6   7
 / \
8   9

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *