Types Of Binary Tree

Types of Binary Tree 

A tree is a binary tree if and only if :– It has a root node , which may not have any child nodes (0 child nodes, NULL tree) – Root node may have 1 or 2 child nodes . Each such node forms a binary tree itself – Number of child nodes can be 0 ,1 ,2.......not more than 2 – There is a unique path from the root to every other node E.g. :-

 A binary tree is a strictly binary tree if and only if :– Each node has exactly two child nodes or no nodes E.g.:-

 A binary tree is a full binary tree if and only if :– Each non leaf node has exactly two child nodes – All leaf nodes are at the same level

[email protected] 9231937821

Page |1

E.g.:-

• A binary tree is a perfect binary tree if and only if :–

is a full binary tree

– All leaf nodes are at the same level E.g.:-

 A binary tree is a complete binary tree (of height h , we take root node as 0 ) if and only if :– Level 0 to h-1 represent a full binary tree of height h-1 – One or more nodes in level h-1 may have 0, or 1 child nodes – If j,k are nodes in level h-1, then j has more child nodes than k if and only if j is to the left of k , i.e. the last level (h) can be missing leaf nodes, however the ones present must be shifted to the left

[email protected] 9231937821

Page |2

E.g.:-

A complete binary tree filled at each depth from left to right

[email protected] 9231937821

Page |3

Preorder Traversal:Step 1 : Start from the root node . Write it down. Step 2 : Now go to the leftmost node from the root node in the left sub tree. On it’s way to the left most node, right down all the nodes as it comes.

Step 3 : When the leftmost node is reached. Write it down. Step 4 : Now visit the right sub tree of the leftmost node’s parent node.

Step 5 : Write down the first node of the right subtree. Step 6 : Now proceed in the same way as in Step

2 - 5 till

‘writing down’ of all the nodes is finished.

•

Inorder Traversal :Step 1 : Start from the root node . Step 2 : Now go to the leftmost node from the root node in the left subtree.

Step 3 : When the leftmost node is reached . Write it down. Step 4 : Now visit/go the leftmost node’s parent node. Write it down.

Step 5 : Now visit/go to

the first node of the right subtree.

Step 6 : Proceed in the same way as in Step

2 - 5 till ‘writing

down’ of all the nodes is finished.

[email protected] 9231937821

Page |4

Postorder Traversal :Step 1 : Start from the root node . Step 2 : Now go to the leftmost node from the root node in the left subtree.

Step 3 : When the leftmost node is reached . Write it down. Step 4 : Now visit/go the leftmost node’s parent node. Step 5 : Now visit/go to

the first node of the right subtree.

Step 6 : Proceed in the same way as in Step

2 - 5 till ‘writing

down’ of all the nodes is finished.

In the above traversals we should follow a rule, which is – In a case when there is no ‘unwritten’ nodes in a subtree (left / right) or there is no subtree (left / right), go backwards from that node, in the reverse way as arrived and ‘go’ to that node that come first in the way back, provided it has not been written. Write it down and proceed.

•

[email protected] 9231937821

Page |5

Example :-

A C E

F G

K

N

M I

Preorder Traversal :- A C E G I F N K M Inorder Traversal :-

ECIGANKFM

Postorder Traversal :- E I G C N M K F A

[email protected] 9231937821

Page |6