Binary Trees

Binary Trees

• Definition of a binary tree: A binary tree is a finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left subtree and right subtree.

•  The binary tree can be as shown below -

Abstract DataType BinT (node * root)

{

Instances : Binary tree is a nonlinear data structure which contains every node except the leaf nodes at most two child nodes.

Operations:

1. Insertion :

This operation is used to insert the nodes in the binary tree. By inserting desired number of nodes, the binary tree gets created.

2. Deletion :

This operation is used to remove any node from the tree. root node is removed the tree becomes empty.

}

1. Types of Binary Tree

Full Binary Tree

•  A full binary tree is a tree in which every node has zero or two children.

•  In other words, the full binary tree is a binary tree in which all the nodes have two children except the leaf node. (Refer Fig. 5.2.3)

Complete Binary Tree

•  The complete binary tree is a binary in which all the levels are completely filled except the last level which is filled from left.

• There are two points to be remembered

1) The leftmost side of the leaf node must always be filled first.

2) It is not necessary for the last leaf node to have right sibling.

• Note that in above representation, Treel is a complete binary tree in which all the levels are completely filled, whereas Tree2 is also a complete binary tree in which the last level is filled from left to right but it is incompletely filled.

Difference between complete binary tree and full binary tree

Left and Right Skewed Trees

The tree in which each node is attached as a left child of parent node then it is left skewed tree. The tree in which each node is attached as a right child of parent node then it is called right skewed tree.