Implementing Binary Tree
Implementing Binary Tree and Traversing
Representing a Binary Tree
Linked Representation of a Binary Tree:
It uses a linked list to implement a binary tree.
Each node in the linked representation holds the following information:
- Data
- Reference to the left child
- Reference to the right child
If a node does not have a left child or a right child or both, the respective left or right child fields of that node points to NULL.
Traversing a Binary Tree
You can implement various operations on a binary tree.
A common operation on a binary tree is traversal.
Traversal refers to the process of visiting all the nodes of a binary tree once.
There are three ways for traversing a binary tree:
- Inorder traversal
- Preorder traversal
- Postorder traversal
Inorder traversal
The following steps are used for traversing a tree in inorder sequence:
1. Traverse the left sub tree.
2. Visit root.
3. Traverse the right sub tree.
Preorder traversal
The following steps are used for traversing a tree in preorder sequence:
1. Visit root.
2. Traverse the left sub tree.
3. Traverse the right sub tree.
Postorder traversal
The following steps are used for traversing a tree in postorder sequence:
1. Traverse the left sub tree.
2. Traverse the right sub tree.
3. Visit the root.
Example:
Postorder Traversal: H D E B F I G C A