Page 206 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 12: Introduction to Trees

The left and right links represent the left and right children respectively, or are null pointers if Notes
the node does not have a left or right child.
We need to maintain an external pointer root to locate the root of the tree.

Self Assessment

Fill in the blanks:
7. Any tree whose nodes can have at the most two children is called a ............................
8. Binary trees can be represented by links, where each node contains the ............................of
the left child and the right child.
9. A node that does not have a left or a right child contains a ............................value in its link
fields.

10. The left and right links represent the ............................if the node does not have a left or
right child.

12.3 Traversal of a Binary Tree

The process of systematically visiting all the nodes in a tree and performing some computation
at each node in the tree is called a tree traversal. When we want to visit each and every element
of a tree, there are three different ways to do the traversal, that is, preorder, inorder and postorder.

!
Caution These traversal methods are limited to Binary trees only and not for any other
tree.

The methods differ primarily in the order in which they visit the root node the nodes in the left
sub-tree and the nodes in the right sub-tree.

Notes A binary tree is of recursive nature, i.e. each sub-tree is a binary tree itself. Hence
the functions used to traverse a tree using these methods can use recursion.

To traverse a non-empty binary tree in pre-order, we need to perform the following three
operations:
Visit the root
Traverse the left sub-tree in pre-order
Traverse the right sub-tree in pre-order
To traverse a non-empty binary tree in in-order, we need to perform the following three
operations:
Traverse the left sub-tree in in-order.

Visit the root
Traverse the right sub-tree in in-order

LOVELY PROFESSIONAL UNIVERSITY 199