Tree Traversal Algorithm in Data Structure

Tree Traversal Algorithm in Data Structure

• 1.
  BIRLA INSTITUTE OF TECHNOLOGY,MESRA JAIPURCAMPUS Presented By: Apoorva Nagar MCA/25013/18 TREE TRAVERSAL ALGORITHMS
• 2.
  TREE TRAVERSAL ALGORITHMS
• 3.
  BINARY TREES • ABinary tree is a tree with all nodes having at most two branches. • Each node have a degree of at most two. • Binary tree can be empty or consists of a root node and two disjoint binary trees termed left subtree and right subtree
• 4.
  BINARY TREE TRAVERSAL •A traversal of a binary tree is where its nodes are visited in a particular but in repetitive order. • A traversal is governed by three action.They are: Move Left(L) Move Right(R) Processed Node(P) • All these action yield into many different combination out of which three most significant combination result into three traversal ways.They are: Inorder Traversal—LPR Postorder Traversal—LRP Preorder Traversal—PLR
• 5.
  INORDER TRAVERSAL ALGORITHM: Recursive procedureto perform Inorder traversal of a binary tree. Procedure INORDER_TRAVERSAL(NODE) If NODE NIL then { call INORDER_TRAVERSAL(LCHILD(NODE)); print (DATA (NODE)); call INORDER_TRAVERSAL(RCHILD(NODE)); } end INORDER_TRAVERSAL.
• 6.
  • The traversalkeeps moving left in the binary tree until one can move no further, processes the node and moves to the right to continue its traversal again. • In the absence of any node to the right, it retracts backward by a node and continue its traversal. • Consider a binary tree Inorder traversal output is: G H F I E A B D C
• 7.
  POSTORDER TRAVERSAL ALGORITHM: Recursive procedureto perform postorder traversal of a binary tree Procedure POSTORDER_TRAVERSAL(NODE) If NODE NIL then { call POSTORDER_TRAVERSAL(LCHILD(NODE)); call POSTORDER_TRAVERSAL(RCHILD(NODE)); print (DATA(NODE)); } end POSTORDER_TRAVERSAL.
• 8.
  • The traversalproceeds by keeping to the left until it is no further possible,turns right to continue its traversal. • If there is no right node, processes the node and retraces its direction by one node to continue its traversal. • Consider a binary tree Postorder Traversal output is: G F E I H D C B A
• 9.
  PREORDER TRAVERSAL ALGORITHM: Recursive procedureto perform preorder traversal of a binary tree Procedure PREORDER_TRAVERSAL(NODE) If NODE NIL then { print (DATA (NODE)); call PREORDER_TRAVERSAL(LCHILD(NODE)); call PREORDER_TRAVERSAL(RCHILD(NODE)); } end PREORDER_TRAVERSAL.
• 10.
  • The traversalprocess every node as it moves to left until it can move no further.Now it turns right to begin again. • If there is no node in the right, retracts until it can move right to continue its traversal. • Consider a binary tree Preorder Traversal output is: A H G I F E B C D
• 11.
  USES OF TREETRAVERSAL In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. Preorder and Inorder traversals are used to create a copy of the tree. Postorder traversal is used to delete the tree.
• 12.
  REFERENCES https://www.geeksforgeeks.org/tree-traversals-inorder- preorder-and-postorder/ https://www.tutorialspoint.com/data_structures_algorithms /tree_traversal.htm
• 13.
  THANK YOU!!!