Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways.
A Tree Data Structure can be traversed in following ways:
- Depth First Search or DFS
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level Order Traversal or Breadth First Search or BFS
- Boundary Traversal
- Diagonal Traversal
Algorithm Inorder(tree)
- Traverse the left subtree, i.e., call Inorder(left->subtree)
- Visit the root.
- Traverse the right subtree, i.e., call Inorder(right->subtree)
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.
Code implementation of Inorder traversal.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* 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);
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
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);
printf("Inorder traversal of binary tree is \n");
printInorder(root);
getchar();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(struct Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
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);
cout << "Inorder traversal of binary tree is \n";
printInorder(root);
return 0;
}
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() { root = null; }
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(node.key + " ");
printInorder(node.right);
}
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);
System.out.println(
"Inorder traversal of binary tree is ");
tree.printInorder(tree.root);
}
}
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def printInorder(root):
if root:
printInorder(root.left)
print(root.val, end=" "),
printInorder(root.right)
if __name__ == "__main__":
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Inorder traversal of binary tree is")
printInorder(root)
using System;
class Node {
public int key;
public Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() { root = null; }
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
Console.Write(node.key + " ");
printInorder(node.right);
}
void printInorder() { printInorder(root); }
static public 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);
Console.WriteLine("Inorder traversal "
+ "of binary tree is ");
tree.printInorder();
}
}
class Node {
constructor(val) {
this.key = val;
this.left = null;
this.right = null;
}
}
var root = null;
function printInorder(node) {
if (node == null)
return;
printInorder(node.left);
console.log(node.key + " ");
printInorder(node.right);
}
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("Inorder traversal of binary tree is ");
printInorder(root);
Output
Inorder traversal of binary tree is 4 2 5 1 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.
Algorithm Preorder(tree)
- Visit the root.
- Traverse the left subtree, i.e., call Preorder(left->subtree)
- Traverse the right subtree, i.e., call Preorder(right->subtree)
Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions on an expression tree.
Code implementation of Preorder traversal:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* 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);
}
void printPreorder(struct node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
printPreorder(node->left);
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);
printf("Preorder traversal of binary tree is \n");
printPreorder(root);
getchar();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
Previous: What is the use of pre-order and post-order traversal ...
Comments
Please Join Us to post.
0