Open In App

DFS traversal of a Tree

Last Updated : 11 Jul, 2025
Suggest changes
Share
47 Likes
Like
Report

Depth-First Search (DFS) is a method used to explore all the nodes in a tree by going as deep as possible along each branch before moving to the next one. It starts at the root node and visits every node in the tree.

Depth-First Search (DFS) can be classified into three main types based on the order in which the nodes are visited:

  • Pre-order Traversal: Visits the root node first, then recursively explores the left and right subtrees.
  • In-order Traversal: Explores the left subtree first, then visits the root, and finally the right subtree.
  • Post-order Traversal: Explores the left and right subtrees first, then visits the root node.
frame_61

Different DFS Traversals of a Tree

1. Inorder Traversal

  • Traverse the left subtree, i.e., call Inorder(left-subtree)
  • Visit the root
  • Traverse the right subtree, i.e., call Inorder(right-subtree)
C++ 
#include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node {  int data;  struct Node *left, *right;  Node(int data)  {  this->data = data;  left = right = NULL;  } }; /* Given a binary tree, print its nodes in inorder*/ void printInorder(struct Node* node) {  if (node == NULL)  return;  /* first recur on left child */  printInorder(node->left);  /* then print the data of node */  cout << node->data << " ";  /* now recur on right child */  printInorder(node->right); } int main() {  struct Node* root = new Node(1);  root->left = new Node(2);  root->right = new Node(3);  root->left->left = new Node(4);  root->left->right = new Node(5);  root->right->right = new Node(6);  printInorder(root);  return 0; }
C 
#include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child  and a pointer to right child */ struct node {  int data;  struct node* left;  struct node* right; }; /* Helper function that allocates a new node with the  given data and NULL left and right pointers. */ struct node* newNode(int data) {  struct node* node  = (struct node*)malloc(sizeof(struct node));  node->data = data;  node->left = NULL;  node->right = NULL;  return (node); } /* Given a binary tree, print its nodes in inorder*/ void printInorder(struct node* node) {  if (node == NULL)  return;  /* first recur on left child */  printInorder(node->left);  /* then print the data of node */  printf("%d ", node->data);  /* now recur on right child */  printInorder(node->right); } int main() {  struct node* root = newNode(1);  root->left = newNode(2);  root->right = newNode(3);  root->left->left = newNode(4);  root->left->right = newNode(5);  root->right->right = newNode(6);  printInorder(root);  getchar();  return 0; }
Java 
class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } class GfG {  // Root of Binary Tree  Node root;  BinaryTree() { root = null; }  /* Given a binary tree, print its nodes in inorder*/  void printInorder(Node node)  {  if (node == null)  return;  /* first recur on left child */  printInorder(node.left);  /* then print the data of node */  System.out.print(node.key + " ");  /* now recur on right child */  printInorder(node.right);  }  // Wrappers over above recursive functions  void printInorder() { printInorder(root); }  public static void main(String[] args)  {  BinaryTree tree = new BinaryTree();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  tree.printInorder();  } }
Python 
class Node: def __init__(self, key): self.left = None self.right = None self.val = key # A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # then print the data of node print(root.val), # now recur on right child printInorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) printInorder(root)
C# 
using System; /* Class containing left and right child of current node and key value*/ class Node {  public int key;  public Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } public class BinaryTree {  // Root of Binary Tree  Node root;  BinaryTree() { root = null; }  /* Given a binary tree, print its nodes in inorder*/  void printInorder(Node node)  {  if (node == null)  return;  /* first recur on left child */  printInorder(node.left);  /* then print the data of node */  Console.Write(node.key + " ");  /* now recur on right child */  printInorder(node.right);  }  // Wrappers over above recursive functions  void printInorder() { printInorder(root); }  public static void Main(String[] args)  {  BinaryTree tree = new BinaryTree();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  tree.printInorder();  } }
JavaScript 
class Node {  constructor(val) {  this.key = val;  this.left = null;  this.right = null;  } }    /* Given a binary tree, print its nodes in inorder */  function printInorder(node) {  if (node == null)  return;  /* first recur on left child */  printInorder(node.left);  /* then print the data of node */  process.stdout.write(node.key + " ");  /* now recur on right child */  printInorder(node.right);  }  var root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  printInorder(root);

Output
Inorder traversal of binary tree is 4 2 5 1 3

Time Complexity: O(N)
Auxiliary Space: O(log N)

Uses of Inorder Traversal

In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.

2. Preorder Traversal

  • Visit the root
  • Traverse the left subtree, i.e., call Preorder(left-subtree)
  • Traverse the right subtree, i.e., call Preorder(right-subtree)
C++ 
#include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node {  int data;  struct Node *left, *right;  Node(int data)  {  this->data = data;  left = right = NULL;  } }; /* Given a binary tree, print its nodes in preorder*/ void printPreorder(struct Node* node) {  if (node == NULL)  return;  /* first print data of node */  cout << node->data << " ";  /* then recur on left subtree */  printPreorder(node->left);  /* now recur on right subtree */  printPreorder(node->right); } int main() {  struct Node* root = new Node(1);  root->left = new Node(2);  root->right = new Node(3);  root->left->left = new Node(4);  root->left->right = new Node(5);  root->right->right = new Node(6);  printPreorder(root);  return 0; }
C 
#include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child  and a pointer to right child */ struct node {  int data;  struct node* left;  struct node* right; }; /* Helper function that allocates a new node with the  given data and NULL left and right pointers. */ struct node* newNode(int data) {  struct node* node  = (struct node*)malloc(sizeof(struct node));  node->data = data;  node->left = NULL;  node->right = NULL;  return (node); } /* Given a binary tree, print its nodes in preorder*/ void printPreorder(struct node* node) {  if (node == NULL)  return;  /* first print data of node */  printf("%d ", node->data);  /* then recur on left subtree */  printPreorder(node->left);  /* now recur on right subtree */  printPreorder(node->right); } int main() {  struct node* root = newNode(1);  root->left = newNode(2);  root->right = newNode(3);  root->left->left = newNode(4);  root->left->right = newNode(5);  root->right->right = newNode(6);  printPreorder(root);  getchar();  return 0; }
Java 
class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } class BinaryTree {  // Root of Binary Tree  Node root;  BinaryTree() { root = null; }  /* Given a binary tree, print its nodes in preorder*/  void printPreorder(Node node)  {  if (node == null)  return;  /* first print data of node */  System.out.print(node.key + " ");  /* then recur on left subtree */  printPreorder(node.left);  /* now recur on right subtree */  printPreorder(node.right);  }  // Wrappers over above recursive functions  void printPreorder() { printPreorder(root); }  // Driver code  public static void main(String[] args)  {  BinaryTree tree = new BinaryTree();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.left.right = new Node(6);  tree.printPreorder();  } }
Python 
class Node: def __init__(self, key): self.left = None self.right = None self.val = key # A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.left.right = Node(6) printPreorder(root)
C# 
using System; /* Class containing left and right child of current node and key value*/ public class Node {  public int key;  public Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } public class BinaryTree {  // Root of Binary Tree  Node root;  BinaryTree() { root = null; }  /* Given a binary tree, print its nodes in preorder*/  void printPreorder(Node node)  {  if (node == null)  return;  /* first print data of node */  Console.Write(node.key + " ");  /* then recur on left subtree */  printPreorder(node.left);  /* now recur on right subtree */  printPreorder(node.right);  }  // Wrappers over above recursive functions  void printPreorder() { printPreorder(root); }  public static void Main()  {  BinaryTree tree = new BinaryTree();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.left.right = new Node(6);    tree.printPreorder();  } }
JavaScript 
// A class that represents an individual node in a // Binary Tree class Node{  constructor(key){  this.left = null  this.right = null  this.val = key  } } // A function to do preorder tree traversal function printPreorder(root){  if(root){  // First print the data of node  process.stdout.write(root.val," ")  // Then recur on left child  printPreorder(root.left)  // Finally recur on right child  printPreorder(root.right)  } } let root = new Node(1) root.left = new Node(2) root.right = new Node(3) root.left.left = new Node(4) root.left.right = new Node(5) printPreorder(root)

Output
Preorder traversal of binary tree is 1 2 4 5 3

Time Complexity: O(N)
Auxiliary Space: O(log N)

Uses of Preorder Traversal

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions of an expression tree.

3. Postorder Traversal

  • Traverse the left subtree, i.e., call Postorder(left-subtree)
  • Traverse the right subtree, i.e., call Postorder(right-subtree)
  • Visit the root


C++ 
// C program for different tree traversals #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node {  int data;  struct Node *left, *right;  Node(int data)  {  this->data = data;  left = right = NULL;  } }; /* Given a binary tree, print its nodes according to the "bottom-up" postorder traversal. */ void printPostorder(struct Node* node) {  if (node == NULL)  return;  // first recur on left subtree  printPostorder(node->left);  // then recur on right subtree  printPostorder(node->right);  // now deal with the node  cout << node->data << " "; } int main() {  struct Node* root = new Node(1);  root->left = new Node(2);  root->right = new Node(3);  root->left->left = new Node(4);  root->left->right = new Node(5);  root->right->right = new Node(6);  printPostorder(root);  return 0; }
C 
#include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child  and a pointer to right child */ struct node {  int data;  struct node* left;  struct node* right; }; /* Helper function that allocates a new node with the  given data and NULL left and right pointers. */ struct node* newNode(int data) {  struct node* node  = (struct node*)malloc(sizeof(struct node));  node->data = data;  node->left = NULL;  node->right = NULL;  return (node); } /* Given a binary tree, print its nodes according to the  "bottom-up" postorder traversal. */ void printPostorder(struct node* node) {  if (node == NULL)  return;  // first recur on left subtree  printPostorder(node->left);  // then recur on right subtree  printPostorder(node->right);  // now deal with the node  printf("%d ", node->data); } int main() {  struct node* root = newNode(1);  root->left = newNode(2);  root->right = newNode(3);  root->left->left = newNode(4);  root->left->right = newNode(5);  root->right->right = newNode(6);  printPostorder(root);  getchar();  return 0; }
Java 
// Java program for different tree traversals /* Class containing left and right child of current  node and key value*/ class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } class BinaryTree {  // Root of Binary Tree  Node root;  BinaryTree() { root = null; }  /* Given a binary tree, print its nodes according to the  "bottom-up" postorder traversal. */  void printPostorder(Node node)  {  if (node == null)  return;  // first recur on left subtree  printPostorder(node.left);  // then recur on right subtree  printPostorder(node.right);  // now deal with the node  System.out.print(node.key + " ");  }  // Wrappers over above recursive functions  void printPostorder() { printPostorder(root); }  public static void main(String[] args)  {  BinaryTree tree = new BinaryTree();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);    tree.printPostorder();  } }
Python 
# Python3 program to for tree traversals # A class that represents an individual node in a # Binary Tree class Node: def __init__(self, key): self.left = None self.right = None self.val = key # A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # the recur on right child printPostorder(root.right) # now print the data of node print(root.val), root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) printPostorder(root)
C# 
// C# program for different tree traversals using System; /* Class containing left and right child of current node and key value*/ public class Node {  public int key;  public Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } } public class BinaryTree {  // Root of Binary Tree  Node root;  BinaryTree() { root = null; }  /* Given a binary tree, print its nodes according to the  "bottom-up" postorder traversal. */  void printPostorder(Node node)  {  if (node == null)  return;  // first recur on left subtree  printPostorder(node.left);  // then recur on right subtree  printPostorder(node.right);  // now deal with the node  Console.Write(node.key + " ");  }  // Wrappers over above recursive functions  void printPostorder() { printPostorder(root); }  public static void Main(String[] args)  {  BinaryTree tree = new BinaryTree();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  tree.printPostorder();  } }
JavaScript 
/* Class containing left and right child of current  node and key value*/ class Node {  constructor(item) {  this.key = item;  this.left = this.right = null;  } } var root;  /*  * Given a binary tree, print its nodes according to the "bottom-up" postorder  * traversal.  */  function printPostorder(node) {  if (node == null)  return;  // first recur on left subtree  printPostorder(node.left);  // then recur on right subtree  printPostorder(node.right);  // now deal with the node  process.stdout.write(node.key + " ");  }  root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  printPostorder(root);

Output
Postorder traversal of binary tree is 4 5 2 3 1

Time Complexity: O(N)
Auxiliary Space: O(log N)

Uses of Postorder Traversal:

Postorder traversal is used to delete every node of the tree. Postorder traversal is also useful to get the postfix expression of an expression tree

Related Article : Breadth First Traversal.


S
Shahnawaz_Ali
Article Tags :

Explore

Lightbox