Page 238 - DCAP407_DATA_STRUCTURE

Unit 12: Binary Tree Traversals and Operations

1. Write a C program to traverse the following algebraic expression in inorder,
postorder and pre-order traversal
(A +B ) – C + ((D * E) + (F/ G) – H)
2. Write a C program to obtain the swapped version of binary tree.

12.6 Summary

• The binary tree can be traversed in various ways. The three major binary tree traversal techniques
are inorder, preorder and postorder traversals.
• The various operations performed on binary tree are insertion, deletion and searching operations.

• The searching operation is related with the insertion operation to identify the location to insert a
node
• In deletion operation, searching method is used to identify the parent node of the deleting node.
12.7 Keywords

Converse Inorder Traversal: The tree obtained after the inorder traversal is represented in the original
tree format.
Infinite Loop: A series of instructions in a computer program which, on execution, result in a cyclic
repetition of the same instructions.
Iterative Traverse: Repetitive traversal.
Traversing Flag: Indicates if the node was visited during traversal.
12.8 Self Assessment

1. State whether the following statements are true or false:
(a) A complete insertion operation of binary tree provides sequential ordering of information in
a tree.
(b) In the post order traversal of binary tree, first the right sub-tree is traversed.

2. Fill in the blanks:
(a) To delete a node in the binary tree, it is important to visit the ………………….. node of the
node to be deleted.
(b) The………………….. method deals with visiting each node in a tree exactly once.
(c) The nodes in the binary tree can be accessed by calculating the ………………… of every
node.
3. Select a suitable choice for every question:
(a) Which among the following traversal of binary tree starts with traversing the root node?
(i) Preorder
(ii) Inorder

(iii) Postorder

LOVELY PROFESSIONAL UNIVERSITY 231