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.
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.
- Visit the root node.
- Traverse the left sub tree in pre-order.
- Traverse the right sub tree in post-order.
Inorder Traversal:
For traversal of a non-empty binary tree or binary search tree in In-order, following sequence of operations is performed.
- Traverse the left sub tree in in-order.
- Visit the root node.
- Traverse the right sub tree in in-order.
Postorder Traversal:
For traversal of a non-empty binary tree or binary search tree in Post-order, following sequence of operations is performed.
- Traverse the left sub tree in post-order.
- Traverse the right sub tree in post-order.
- Visit the root node.
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 Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
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
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- C| C++| Java
- Spiral Order traversal of Tree- C | C++| 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.- C| C++| 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- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
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
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- C| C++| Java
- Spiral Order traversal of Tree- C | C++| 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.- C| C++| 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- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | 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
Login/Signup to comment