Tree Traversals: Depth First Search (DFS)

Tree Traversals: Depth First Search (DFS)

The term traversal means to visit each node in a tree exactly once. In linear lists the order of traversal is vividly first to last. However, in trees there exists no such natural linear order.In this article, depth first search is studied.

Tree Traversals - Depth First Search (DFS)

More Information About DFS:

DFS can be defined as an algorithm, based on backtracking, dedicated to traversing a tree structure by first visiting the root first and then the left sub-tree and the right sub-tree.

  • It is of three types:
    • In-order traversal.

    • Pre-order traversal.

    • Post-order traversal.

Preorder Traversal:

For traversal of a non-empty binary tree or binary search tree in Pre-order, following sequence of operations is performed.

  1. Visit the root node.
  2. Traverse the left sub tree in pre-order.
  3. Traverse the right sub tree in post-order.
Preorder Tree Traversal in binary tree in C++

Inorder Traversal:

For traversal of a non-empty binary tree or binary search tree in In-order, following sequence of operations is performed.

  1. Traverse the left sub tree in in-order.
  2. Visit the root node.
  3. Traverse the right sub tree in in-order.
Inorder Tree traversal in binary tree in cpp

Postorder Traversal:

For traversal of a non-empty binary tree or binary search tree in Post-order, following sequence of operations is performed.

  1. Traverse the left sub tree in post-order.
  2. Traverse the right sub tree in post-order.
  3. Visit the root node.
postorder-tree-traversal-in-binary-tree

Code Implementation for Tree Traversal : Depth-First Search (DFS) in C++

Run
#include<bits/stdc++.h>
using namespace std;
class Tree
{
public:
  int data;
  Tree *left = NULL, *right = NULL;
  // Constructor initialised
    Tree (int x)
  {
    data = x;
    left = NULL;
    right = NULL;
  }
};
void preorder_traversal (Tree * root)
{
  if (root == NULL)
    return;
  // Print the data
  cout << root->data << " "; // Visit Left subtree preorder_traversal (root->left);
  // Visit right subtree
  preorder_traversal (root->right);
}

void inorder_traversal (Tree * root)
{
  if (root == NULL)
    return;
  // Visit Left subtree
  inorder_traversal (root->left);
  // Print the data
  cout << root->data << " "; // Visit right subtree inorder_traversal (root->right);
}

void postorder_traversal (Tree * root)
{
  if (root == NULL)
    return;
  // Visit Left subtree
  postorder_traversal (root->left);
  // Visit right subtree
  postorder_traversal (root->right);
  // Print the data
  cout << root->data << " "; } int main () { Tree *root = new Tree (17); root->left = new Tree (10);
  root->right = new Tree (11);
  root->left->left = new Tree (7);
  root->right->left = new Tree (27);
  root->right->right = new Tree (9);
  cout << "Preorder => ";
  preorder_traversal (root);
  cout << endl;
  cout << "Inorder => ";
  inorder_traversal (root);
  cout << endl;
  cout << "Postorder => ";
  postorder_traversal (root);
  cout << endl;
  return 0;
}
Output:

Preorder => 17 10 7 11 27 9 
Inorder => 7 10 17 27 11 9 
Postorder => 7 10 27 9 11 17

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal Line by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric – C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree- CC++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal LIne by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric  C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree. CC++ | Java

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription