Tree Traversal in Data structure | Inorder traversal | Preorder Traversal |Post order Traversal

 

Tree Traversal

  • A Tree is a non-linear data structure in which elements are arranged in a hierarchical structure.
  • Tree Traversal is the process of visiting each node of a tree exactly once in a particular order.
  • Tree traversal is used to process, search, display and perform operations on the nodes of a tree.
Types of Tree Traversal
  1. Preorder Traversal (Root → Left → Right)
  2. Inorder Traversal (Left → Root → Right)
  3. Postorder Traversal (Left → Right → Root)
Preorder Traversal :
In Preorder Traversal, the root node is visited first, followed by the left subtree and then the right subtree.

Order
Root → Left → Right

Example

        A
       / \
      B   C
     / \
    D   E
Step 1: Visit A
Step 2: Move to the left subtree and visit B
Step 3: Visit B's left child D
Step 4: Visit B's right child E
Step 5: Move to the right subtree and visit C
Therefore, Preorder = A → B → D → E → C

Preorder Algorithm

Preorder(node)
  If node is not NULL
       Visit node
       Preorder(node → left)
       Preorder(node → right)


Inorder Traversal:
In Inorder Traversal, the left subtree is visited first, followed by the root node and then the right subtree.

Order
Left → Root → Right

Example

        A
       / \
      B   C
     / \
    D   E

Step 1: Move to the leftmost node D and visit D
Step 2: Return to B and visit B
Step 3: Visit B's right child E
Step 4: Return to A and visit A
Step 5: Move to the right subtree and visit C

Therefore, Inorder = D → B → E → A → C

Inorder Algorithm

Inorder(node)
   If node is not NULL
        Inorder(node → left)
        Visit node
         Inorder(node → right)


Postorder Traversal:
In Postorder Traversal, the left subtree is visited first, followed by the right subtree, and the root node is visited last.

Order
Left → Right → Root

Example

        A
       / \
      B   C
     / \
    D   E
Step 1: Visit D
Step 2: Visit E
Step 3: Visit B
Step 4: Visit C
Step 5: Finally visit A

Therefore, Postorder = D → E → B → C → A

Postorder Algorithm
Postorder(node)
     If node is not NULL
         Postorder(node → left)
         Postorder(node → right)
         Visit node


Applications of Tree Traversal
  • Preorder: Used to create a copy of a tree and represent the structure of a tree.
  • Inorder: Used in Binary Search Trees to obtain elements in sorted order.
  • Postorder: Useful when deleting a tree because child nodes can be processed before the parent node.
  • Tree traversal is also used in expression trees, searching, file systems and other hierarchical data processing.

Read Next Topics:
Tree Traversal → BST → B Tree → B+ Tree

Handwritten Notes- Download PDF

Video Explanation- Watch on YouTube




Comments

Post a Comment

Popular posts from this blog

B+ Tree in DBMS | B+ Tree in Data Structure

    B+  Tree A B+ Tree is a self-balancing multi-way search tree   All leaf nodes are present at the same level . Actual data records are stored only in the leaf nodes . Internal nodes contain only search keys . It is mainly used for efficient searching and sequential access . B+ Tree supports efficient range queries . Structure of B+ Tree Consider a B+ Tree node containing keys and children: Number of Keys Number of Children 1 2 2 3 3 4 In general, Number of children = Number of keys + 1 The leaf nodes are connected sequentially using links( Linked List ). Rules of B+ Tree For a B+ Tree of order m : At most: A node can have at most m children . A node can contain at most m − 1 keys. At least: An internal node must have at least [ m/2 ] children . An internal node must contain at least [ m/2 ] − 1 keys . Insertion...
Read more

Normalization in DBMS,(1NF,2NF,3NF,BCNF,4NF,5NF)

                      Normalization in DBMS Normalization divides a large table into smaller , logically related tables and connects them using appropriate keys. The main purpose of normalization is to reduce unnecessary duplication of data and prevent problems that may occur when data is inserted, updated, or deleted. 1. First Normal Form (1NF) A relation is said to be in First Normal Form (1NF) when every attribute contains a single, indivisible value . Conditions of   1 NF Each cell must contain only one value. Multiple values should not be stored in the same field. ·         Example Customer Items Purchased Gowsi Rice, Dal Tamil Soap ·   Here, the Items Purchased column contains more than one value for Gowsi . ·   Therefore, the table is not in 1 NF . Converting it into 1NF. ...
Read more

Hashing in Data Structure | Collision Resolution Techniques | Hashing in DBMS

  Hashing in DBMS Hashing is a technique used to map data elements (keys) to specific locations in a hash table using a hash function. It allows insertion and retrieval of data efficiently     Hash Function A hash function converts a key into a hash code (index) , which is used to store and retrieve the data from a hash table.                                 h(k)=k mod m Where: k → Key m → Hash table size h(k) → Hash index  Hash Table A hash table is a data structure that stores data in an array format . Each position in the table is called a bucket , and the position is accessed using the hash function. Example Consider Keys                   (k) = 11, 18, 20, 25, 29, 33 Hash table size (m) = 7 Hash function:    h(k)=k mod m                     ...
Read more