Question

Exercise 1: (Divide and Conquer: Binary tree traversal)

Write pseudocode for one of the classic traversal algorithms (preorder, inorder, and postorder) for binary trees. Assuming that your algorithm is recursive, find the number of recursive calls made.

Answer 1

Preorder Pseudocode

Algorithm

Algorithm Preorder(T)
//Implements the preorder traversal of a binary tree
//Input: Binary tree T (with labeled vertices)
//Output: Node labels listed in preorder
if T = ∅
print label of T’s root
Preorder(TL) //TL is the root’s left subtree
Preorder(TR) //TR is the root’s right subtree

Inorder Pseudo code

Algorithm Inorder(tree)
//Implements the preorder traversal of a binary tree
//Input: Binary tree T (with labeled vertices)
   1. Traverse the left subtree, i.e., call Inorder(left-subtree)
   2. Visit the root.
   3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Algorithm Postorder(tree)
//Implements the preorder traversal of a binary tree
//Input: Binary tree T (with labeled vertices)
   1. Traverse the left subtree, i.e., call Postorder(left-subtree)
   2. Traverse the right subtree, i.e., call Postorder(right-subtree)
   3. Visit the root.

Comment Down if any Query

Pleause Thumbs up if you satisfy with Answer