Tree Traversal Techniques

-


Traversal is the method of processing each and every node in the Binary Search Tree exactly once in a systematic manner.
There are three different types of tree traversal.
(1) Preorder Traversal 
(2) In order Traversal 
(3) Post order Traversal

PreOrder Traversal

Steps for Preorder Traversal:
(1) Process the root node first.
(2) Traverse the left sub tree in preorder.
(3) Traverse the right sub tree in preorder.

InOrder Traversal

Steps for Inorder Traversal:
(1) Traverse the left sub tree in inorder.
(2) Process the root node.
(3) Traverse the right sub tree in inorder.

PostOrder Traversal

Steps for PostOrder Traversal:
(1) Traverse the left sub tree in Post order.
(2) Traverse the right sub tree in Post order.
(3) Process the root node.
Now Consider Following Example
PreOrder Traversal : A B D E C F G 
InOrder Traversal : D B E A F C G
PostOrder Traversal : D E B F G C A

Comments

Post a Comment

Thanks for comment. We will get back to you soon...

Popular posts from this blog

Difference between Array and Linked List

-
Image
Linked List vs. Array Array is a datatype which is widely implemented as a default type, in almost all the modern programming languages, and is used to store data of similar type. But there are many usecases, like the one where we don't know the quantity of data to be stored, for which advanced data structures are required, and one such data structure is  linked list . Let's understand how array is different from Linked list. ARRAY LINKED LIST Array is a collection of elements of similar data type. Linked List is an ordered collection of elements of same type, which are connected to each other using pointers. Array supports  Random Access , which means elements can be accessed directly using their index, like  arr[0]  for 1st element,  arr[6]  for 7th element etc. Hence, accessing elements in an array is  fast  with a constant time complexity of  O(1) . Linked List supports  Sequential Access , which means to access any element/node in a linked list, we have to
Read more

What is a Queue Data Structure?

-
Image
What is a Queue Data Structure? Queue  is also an abstract data type or a linear data structure, just like stack data structure, in which the first element is inserted from one end called the  REAR (also called  tail ), and the removal of existing element takes place from the other end called as  FRONT (also called  head ). This makes queue as  FIFO (First in First Out) data structure, which means that element inserted first will be removed first. Which is exactly how queue system works in real world. If you go to a ticket counter to buy movie tickets, and are first in the queue, then you will be the first one to get the tickets. Right? Same is the case with Queue data structure. Data inserted first, will leave the queue first. The process to add an element into queue is called  Enqueue  and the process of removal of an element from queue is called  Dequeue . Basic features of Queue Like stack, queue is also an ordered list of elements of similar data types. Queue is
Read more