1 of 19

SUBJECT: ANALYSIS AND DESIGN OF ALGORITHM

​

TOPIC: TREE TRAVERSAL

Cardamom Planters’ Association College

Pankajam Nagar, Bodinayakanur – 625513

​

Department CS & IT

​

2025-2026

​

Presented by

L.Sathiya.,M.Sc.,M.Phil.,

Assistant professor

Department of & CS & IT

2 of 19

CONTENTS

  • Tree Traversal
  • Preorder Traversal
  • Inorder Traversal
  • Postorder Traversal
  • Applications of Binary Trees

3 of 19

TREE TRAVERSAL

  • Tree Traversal refers to the process of visiting each node in a tree data structure exactly once.

4 of 19

DEPTH FIRST TRAVERSAL

  • Following three traversal techniques fall under Depth First Traversal-
  • Preorder Traversal
  • Inorder Traversal
  • Postorder Traversal

5 of 19

1. PREORDER TRAVERSAL

  • Algorithm-
  • Visit the root
  • Traverse the left sub tree i.e. call Preorder (left sub tree)
  • Traverse the right sub tree i.e. call Preorder (right sub tree)
  • Root → Left → Right

6 of 19

EXAMPLE

7 of 19

  • Applications-
  • Preorder traversal is used to get prefix expression of an expression tree.
  • Preorder traversal is used to create a copy of the tree.

8 of 19

2. INORDER TRAVERSAL

  • Algorithm-
  • Traverse the left sub tree i.e. call Inorder (left sub tree)
  • Visit the root
  • Traverse the right sub tree i.e. call Inorder (right sub tree)
  • Left → Root → Right

9 of 19

EXAMPLE-

10 of 19

  • Application-
  • Inorder traversal is used to get infix expression of an expression tree.

11 of 19

3. POSTORDER TRAVERSAL-

  • Algorithm-
  • Traverse the left sub tree i.e. call Postorder (left sub tree)
  • Traverse the right sub tree i.e. call Postorder (right sub tree)
  • Visit the root

​

  • Left → Right → Root

12 of 19

EXAMPLE-

13 of 19

  • Applications-
  • Postorder traversal is used to get postfix expression of an expression tree.
  • Postorder traversal is used to delete the tree.
  • This is because it deletes the children first and then it deletes the parent.

14 of 19

BREADTH FIRST TRAVERSAL-

  • Breadth First Traversal of a tree prints all the nodes of a tree level by level.
  • Breadth First Traversal is also called as Level Order Traversal.

15 of 19

EXAMPLE

16 of 19

  • Application-
  • Level order traversal is used to print the data in the same order as stored in the array representation of a complete binary tree.

17 of 19

BINARY TREE PROPERTIES-

  • Property-01:
  • Minimum number of nodes in a binary tree of height H= H + 1
  • Property-02:
  • Maximum number of nodes in a binary tree of height H= 2H+1 – 1

18 of 19

Property-03:

Total Number of leaf nodes in a Binary Tree

    • = Total Number of nodes with 2 children + 1

Property-04:

Maximum number of nodes at any level ‘L’ in

a binary tree= 2L

19 of 19

THANKYOU