|
Binary trees are fundamental data structures in computer science and understanding their traversal is crucial for various applications. Traversing a binary tree means visiting all the nodes in a specific order. There are several traversal methods, each with its unique applications and benefits. This article will explore the main types of binary tree traversal: in-order, pre-order, post-order, and level-order.
Types of Binary Tree TraversalIn in-order traversal, the left child is visited first, followed by the node itself, and then the right child. This can be visualized as Left – Root – Right.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data) {
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
void preOrderTraversal(Node* root) {
if (root == nullptr) return;
// Visit the root node
cout << root->data << " ";
// Traverse the left subtree
preOrderTraversal(root->left);
// Traverse the right subtree
preOrderTraversal(root->right);
}
int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
cout << "Pre-Order Traversal: ";
preOrderTraversal(root);
cout << endl;
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
void inOrderTraversal(struct Node* root) {
if (root == NULL) return;
// Traverse the left subtree
inOrderTraversal(root->left);
// Visit the root node
printf("%d ", root->data);
// Traverse the right subtree
inOrderTraversal(root->right);
}
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;
}
int main() {
struct Node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("In-Order Traversal: ");
inOrderTraversal(root);
printf("\n");
return 0;
}
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void inOrderTraversal(Node root) {
if (root == null) return;
// Traverse the left subtree
inOrderTraversal(root.left);
// Visit the root node
System.out.print(root.data + " ");
// Traverse the right subtree
inOrderTraversal(root.right);
}
public static void main(String[] args) {
Node root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
System.out.print("In-Order Traversal: ");
inOrderTraversal(root);
System.out.println();
}
}
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def in_order_traversal(root):
if root is None:
return
# Traverse the left subtree
in_order_traversal(root.left)
# Visit the root node
print(root.data, end=" ")
# Traverse the right subtree
in_order_traversal(root.right)
if __name__ == "__main__":
root = Node(2)
root.left = Node(1)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("In-Order Traversal: ", end="")
in_order_traversal(root)
print()
using System;
class Node {
public int data;
public Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void InOrderTraversal(Node root) {
if (root == null) return;
// Traverse the left subtree
InOrderTraversal(root.left);
// Visit the root node
Console.Write(root.data + " ");
// Traverse the right subtree
InOrderTraversal(root.right);
}
static void Main(string[] args) {
Node root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
Console.Write("In-Order Traversal: ");
InOrderTraversal(root);
Console.WriteLine();
}
}
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function inOrderTraversal(root) {
if (root === null) return;
// Traverse the left subtree
inOrderTraversal(root.left);
// Visit the root node
console.log(root.data + " ");
// Traverse the right subtree
inOrderTraversal(root.right);
}
// Driver Code
let root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
// Perform inorder traversal
console.log("In-Order Traversal:");
inOrderTraversal(root);
OutputPre-Order Traversal: 1 2 4 5 3
Time Complexity: O(N)
Auxiliary Space: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.
Below are some important concepts in In-order Traversal:
In pre-order traversal, the node is visited first, followed by its left child and then its right child. This can be visualized as Root – Left – Right.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data) {
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
void preOrderTraversal(Node* root) {
if (root == nullptr) return;
// Visit the root node
cout << root->data << " ";
// Traverse the left subtree
preOrderTraversal(root->left);
// Traverse the right subtree
preOrderTraversal(root->right);
}
int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
cout << "Pre-Order Traversal: ";
preOrderTraversal(root);
cout << endl;
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
void preOrderTraversal(struct Node* root) {
if (root == NULL) return;
// Visit the root node
printf("%d ", root->data);
// Traverse the left subtree
preOrderTraversal(root->left);
// Traverse the right subtree
preOrderTraversal(root->right);
}
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;
}
int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Pre-Order Traversal: ");
preOrderTraversal(root);
printf("\n");
return 0;
}
class Node {
int data;
Node left, right;
// Constructor
Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void preOrderTraversal(Node root) {
if (root == null) return;
// Visit the root node
System.out.print(root.data + " ");
// Traverse the left subtree
preOrderTraversal(root.left);
// Traverse the right subtree
preOrderTraversal(root.right);
}
public static void main(String[] args) {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
System.out.print("Pre-Order Traversal: ");
preOrderTraversal(root);
System.out.println();
}
}
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def pre_order_traversal(root):
if root is None:
return
# Visit the root node
print(root.data, end=" ")
# Traverse the left subtree
pre_order_traversal(root.left)
# Traverse the right subtree
pre_order_traversal(root.right)
if __name__ == "__main__":
# Create the following binary tree
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Pre-Order Traversal: ", end="")
pre_order_traversal(root)
print()
using System;
class Node {
public int data;
public Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void PreOrderTraversal(Node root) {
if (root == null) return;
// Visit the root node
Console.Write(root.data + " ");
// Traverse the left subtree
PreOrderTraversal(root.left);
// Traverse the right subtree
PreOrderTraversal(root.right);
}
static void Main(string[] args) {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
Console.Write("Pre-Order Traversal: ");
PreOrderTraversal(root);
Console.WriteLine();
}
}
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function preOrderTraversal(root) {
if (root === null) return;
// Visit the root node
console.log(root.data + " ");
// Traverse the left subtree
preOrderTraversal(root.left);
// Traverse the right subtree
preOrderTraversal(root.right);
}
// Driver Code
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);
console.log("Pre-Order Traversal:");
preOrderTraversal(root);
OutputPre-Order Traversal: 1 2 4 5 3
Time Complexity: O(N)
Auxiliary Space: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.
Below are some important concepts in Pre-Order Traversal:
In post-order traversal, the left child is visited first, then the right child, and finally the node itself. This can be visualized as Left – Right – Root.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data) {
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
void postOrderTraversal(Node* root) {
if (root == nullptr) return;
// Traverse the left subtree
postOrderTraversal(root->left);
// Traverse the right subtree
postOrderTraversal(root->right);
// Visit the root node
cout << root->data << " ";
}
int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
cout << "Post-Order Traversal: ";
postOrderTraversal(root);
cout << endl;
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
void postOrderTraversal(struct Node* root) {
if (root == NULL) return;
// Traverse the left subtree
postOrderTraversal(root->left);
// Traverse the right subtree
postOrderTraversal(root->right);
// Visit the root node
printf("%d ", root->data);
}
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;
}
int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Post-Order Traversal: ");
postOrderTraversal(root);
printf("\n");
return 0;
}
class Node {
int data;
Node left, right;
// Constructor
Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void postOrderTraversal(Node root) {
if (root == null) return;
// Traverse the left subtree
postOrderTraversal(root.left);
// Traverse the right subtree
postOrderTraversal(root.right);
// Visit the root node
System.out.print(root.data + " ");
}
public static void main(String[] args) {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
System.out.print("Post-Order Traversal: ");
postOrderTraversal(root);
System.out.println();
}
}
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def post_order_traversal(root):
if root is None:
return
# Traverse the left subtree
post_order_traversal(root.left)
# Traverse the right subtree
post_order_traversal(root.right)
# Visit the root node
print(root.data, end=" ")
if __name__ == "__main__":
# Create the following binary tree
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Post-Order Traversal: ", end="")
post_order_traversal(root)
print()
using System;
class Node {
public int data;
public Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void PostOrderTraversal(Node root) {
if (root == null) return;
// Traverse the left subtree
PostOrderTraversal(root.left);
// Traverse the right subtree
PostOrderTraversal(root.right);
// Visit the root node
Console.Write(root.data + " ");
}
static void Main(string[] args) {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
Console.Write("Post-Order Traversal: ");
PostOrderTraversal(root);
Console.WriteLine();
}
}
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function postOrderTraversal(root) {
if (root === null) return;
// Traverse the left subtree
postOrderTraversal(root.left);
// Traverse the right subtree
postOrderTraversal(root.right);
// Visit the root node
console.log(root.data + " ");
}
// Driver Code
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);
console.log("Post-Order Traversal:");
postOrderTraversal(root);
OutputPost-Order Traversal: 4 5 2 3 1
Below are some important concepts in Post-Order Traversal:
In level-order traversal, the nodes are visited level by level, starting from the root node and then moving to the next level. This can be visualized as Level 1 – Level 2 – Level 3 – ….
C++
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data) {
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
void levelOrderTraversal(Node* root) {
if (root == nullptr) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
// Visit the root node
cout << current->data << " ";
// Enqueue left child
if (current->left != nullptr) q.push(current->left);
// Enqueue right child
if (current->right != nullptr) q.push(current->right);
}
}
int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
cout << "Level-Order Traversal: ";
levelOrderTraversal(root);
cout << endl;
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct QueueNode {
struct Node* treeNode;
struct QueueNode* next;
};
void enqueue(struct QueueNode** front, struct QueueNode** rear, struct Node* treeNode) {
struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
newNode->treeNode = treeNode;
newNode->next = NULL;
if (*rear == NULL) {
*front = *rear = newNode;
return;
}
(*rear)->next = newNode;
*rear = newNode;
}
struct Node* dequeue(struct QueueNode** front, struct QueueNode** rear) {
if (*front == NULL) return NULL;
struct Node* treeNode = (*front)->treeNode;
struct QueueNode* temp = *front;
*front = (*front)->next;
if (*front == NULL) *rear = NULL;
free(temp);
return treeNode;
}
int isEmpty(struct QueueNode* front) {
return front == NULL;
}
void levelOrderTraversal(struct Node* root) {
if (root == NULL) return;
struct QueueNode* front = NULL;
struct QueueNode* rear = NULL;
enqueue(&front, &rear, root);
while (!isEmpty(front)) {
struct Node* current = dequeue(&front, &rear);
// Visit the root node
printf("%d ", current->data);
// Enqueue left child
if (current->left != NULL) enqueue(&front, &rear, current->left);
// Enqueue right child
if (current->right != NULL) enqueue(&front, &rear, current->right);
}
}
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;
}
int main() {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Level-Order Traversal: ");
levelOrderTraversal(root);
printf("\n");
return 0;
}
import java.util.LinkedList;
import java.util.Queue;
class Node {
int data;
Node left, right;
// Constructor
Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void levelOrderTraversal(Node root) {
if (root == null) return;
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node current = q.poll();
// Visit the root node
System.out.print(current.data + " ");
// Enqueue left child
if (current.left != null) q.add(current.left);
// Enqueue right child
if (current.right != null) q.add(current.right);
}
}
public static void main(String[] args) {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
System.out.print("Level-Order Traversal: ");
levelOrderTraversal(root);
System.out.println();
}
}
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def level_order_traversal(root):
if root is None:
return
q = deque([root])
while q:
current = q.popleft()
# Visit the root node
print(current.data, end=" ")
# Enqueue left child
if current.left:
q.append(current.left)
# Enqueue right child
if current.right:
q.append(current.right)
if __name__ == "__main__":
# Create the following binary tree
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Level-Order Traversal: ", end="")
level_order_traversal(root)
print()
using System;
using System.Collections.Generic;
class Node {
public int data;
public Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class GFG {
public static void LevelOrderTraversal(Node root) {
if (root == null) return;
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count > 0) {
Node current = q.Dequeue();
// Visit the root node
Console.Write(current.data + " ");
// Enqueue left child
if (current.left != null) q.Enqueue(current.left);
// Enqueue right child
if (current.right != null) q.Enqueue(current.right);
}
}
static void Main(string[] args) {
// Create the following binary tree
// 1
// / \
// 2 3
// / \
// 4 5
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);
Console.Write("Level-Order Traversal: ");
LevelOrderTraversal(root);
Console.WriteLine();
}
}
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function levelOrderTraversal(root) {
if (root === null) return;
let queue = [root];
while (queue.length > 0) {
let current = queue.shift();
// Visit the root node
console.log(current.data + " ");
// Enqueue left child
if (current.left !== null) queue.push(current.left);
// Enqueue right child
if (current.right !== null) queue.push(current.right);
}
}
// Driver Code
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);
console.log("Level-Order Traversal:");
levelOrderTraversal(root);
OutputLevel-Order Traversal: 1 2 3 4 5
Below are some important concepts in Level-Order Traversal:
Special Binary Tree Traversals Quick Links :
|
Linked List Data Structure