×

Courses

Chapters

>
<

Aptitude

Tree Traversals in Binary Tree

Tree Traversals in Binary Tree

There are three most popular ways in which we can traverse a binary tree which are –

  1. Inorder
  2. Postorder
  3. Preorder

How each of the Postorder, Inorder, Preorder work?
Inorder

  • Traverse the left sub-tree, (recursively call inorder(root -> left).
  • Visit and print the root node.
  • Traverse the right sub-tree, (recursively call inorder(root -> right).

Tips to remember –

  • Direction : Clockwise direction
  • Rule : LCR i.e. Left Center(root) Right

Preorder

  • Visit and print the root node.
  • Traverse the left sub-tree, (recursively call Preorder(root -> left).
  • Traverse the right sub-tree, (recursively call Preorder(root -> right)

Tips to remember –

  • Direction : Anti-Clockwise direction
  • Rule : CLR i.e. Center(root) left Right

Postorder

  • Traverse the left sub-tree, (recursively call Postorder(root -> left).
  • Traverse the right sub-tree, (recursively call Postorder(root -> right).
  • Visit and print the root node

Tips to remember –

  • Direction : Anti-Clockwise direction
  • Rule : LRC i.e.  Left Right Center(root)

Code for Inorder PostOrder PreOrder in Binary Tree
  

#include <stdio.h>
#include <stdlib.h>

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// preorderTraversal traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// postorderTraversal traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Create a new Node
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 2);
  insertRight(root, 8);

  insertLeft(root->left, 4);
  insertRight(root->left, 3);

  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);

  printf("\nPostorder traversal \n");
  postorderTraversal(root);
}
  

  

#include <iostream>
using namespace std;

struct Node {
  int data;
  struct Node *left, *right;
  Node(int data) {
    this->data = data;
    left = right = NULL;
  }
};

// Preorder traversal
void preorderTraversal(struct Node* node) {
  if (node == NULL)
    return;

  cout << node->data << "->";
  preorderTraversal(node->left);
  preorderTraversal(node->right);
}

// Postorder traversal
void postorderTraversal(struct Node* node) {
  if (node == NULL)
    return;

  postorderTraversal(node->left);
  postorderTraversal(node->right);
  cout << node->data << "->";
}

// Inorder traversal
void inorderTraversal(struct Node* node) {
  if (node == NULL)
    return;

  inorderTraversal(node->left);
  cout << node->data << "->";
  inorderTraversal(node->right);
}

int main() {
  struct Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(8);
  root->left->left = new Node(4);
  root->left->right = new Node(3);

  cout << "Inorder traversal ";
  inorderTraversal(root);

  cout << "\nPreorder traversal ";
  preorderTraversal(root);

  cout << "\nPostorder traversal ";
  postorderTraversal(root);
}
  

  

class Node {
  int item;
  Node left, right;

  public Node(int key) {
  item = key;
  left = right = null;
  }
}

class BinaryTree {
  // Root of Binary Tree
  Node root;

  BinaryTree() {
  root = null;
  }

  void postorder(Node node) {
  if (node == null)
    return;

  // Traverse left
  postorder(node.left);
  // Traverse right
  postorder(node.right);
  // Traverse root
  System.out.print(node.item + "->");
  }

  void inorder(Node node) {
  if (node == null)
    return;

  // Traverse left
  inorder(node.left);
  // Traverse root
  System.out.print(node.item + "->");
  // Traverse right
  inorder(node.right);
  }

  void preorder(Node node) {
  if (node == null)
    return;

  // Traverse root
  System.out.print(node.item + "->");
  // Traverse left
  preorder(node.left);
  // Traverse right
  preorder(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(8);
  tree.root.left.left = new Node(4);
  tree.root.left.right = new Node(3);

  System.out.println("Inorder traversal");
  tree.inorder(tree.root);

  System.out.println("\nPreorder traversal ");
  tree.preorder(tree.root);

  System.out.println("\nPostorder traversal");
  tree.postorder(tree.root);
  }
}

Output : C

	
Inorder traversal 
4 ->2 ->3 ->1 ->8 ->
Preorder traversal 
1 ->2 ->4 ->3 ->8 ->
Postorder traversal 
4 ->3 ->2 ->8 ->1 ->

Output : C++

	
Inorder traversal 4->2->3->1->8->
Preorder traversal 1->2->4->3->8->
Postorder traversal 4->3->2->8->1->

Output : Java

	
Inorder traversal
5->12->6->1->9->
Preorder traversal 
1->12->5->6->9->
Postorder traversal
5->6->12->9->1->
→
←