Ashok's Blog

Binary Tree

Ashok's photo
Ashok

A binary tree is a tree data structure in which each node can have either zero , one or at most two children nodes. The two children are referred to as a left and right child respectively.

Binary_tree_v2.png

By Radke7CB - Own work, CC BY-SA 4.0, commons.wikimedia.org/w/index.php?curid=114..

The top most node is known as the root node , while nodes with no children are known as leaf nodes.

Types of Binary Trees

There are various types of binary trees, and each of these binary tree types has unique characteristics.

1. Full Binary Tree

Full Binary tree is a binary tree where every node except the leaf node has two children.

Full_binary.png

By Tmigler, CC BY-SA 4.0, commons.wikimedia.org/w/index.php?curid=659..

In a full binary tree, if there are n number of total nodes –

  • The number of internal nodes(Node with at least one child) is given by (n-1)/2
  • The number of leaf nodes is given by (n+1)/2

2. Complete Binary Tree

A complete Binary tree is a Binary tree in which all the levels are completely filled except the last level that may or may not be completely filled. Elements are filled from left to right.

Complete_binary2.png

By jmatocha, CC BY-SA 4.0, commons.wikimedia.org/w/index.php?curid=839..

3. Perfect Binary Trees

There are exactly two children on each internal node in a perfect binary tree, and all the leaves are on the same level.

PerfectBinaryTree.png

4.Balanced Binary Trees

A binary tree is said to be balanced if the height of the left and the right subtrees differ by 0 or 1.

Balanced.png

Right subtree height is 3, left subtree height is 2. The difference between the two subtree heights is 1, so this tree is a balanced binary.

5. Degenerate Binary Tree

A degenerate (or pathological) tree is where each parent node has only one associated child node.This means that the tree will behave like a linked list data structure.

DegeneratedTree.png

A binary tree has almost twice as many nodes at each level as at the previous level. Therefore, the minimum height of a binary tree is almost equal to log(n).

Benefits of Binary Trees

  • Binary trees are used in binary search trees to find elements more quickly and efficiently.

  • A binary tree is also used in heaps, which are special kinds of binary trees. Heaps are used in heap sort, which is an efficient sorting algorithm. Heaps are also used in priority queues, which are queues arranged according to importance.

  • Binary trees are used in converting different prefix and postfix expressions.

data structures