×

Courses

Chapters

>
<

Data Structure

Tree Traversal | CrackEase

Tree Traversals in Binary Tree

Tree Traversals in Binary Tree

There are three commonly used depth-first traversals for binary trees:

  1. Inorder
  2. Preorder
  3. Postorder
How Inorder, Preorder and Postorder work
Inorder
  • Traverse left subtree (inorder(root->left)).
  • Visit root.
  • Traverse right subtree (inorder(root->right)).

Rule: L - Root - R (Left, Center, Right)

Preorder
  • Visit root.
  • Traverse left subtree (preorder(root->left)).
  • Traverse right subtree (preorder(root->right)).

Rule: Root - L - R (Center, Left, Right)

Postorder
  • Traverse left subtree (postorder(root->left)).
  • Traverse right subtree (postorder(root->right)).
  • Visit root.

Rule: L - R - Root (Left, Right, Center)

preorder traversal
inorder traversal
postorder traversal
Code for Inorder, Preorder & Postorder (examples)
  
#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);
}

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

// Postorder 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(int value) {
  struct node* newNode = (struct node*)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);

  return 0;
}
  

  
#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);

  return 0;
}
  

  
class Node {
  int item;
  Node left, right;

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

class BinaryTree {
  Node root;

  BinaryTree() { root = null; }

  void postorder(Node node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    System.out.print(node.item + "->");
  }

  void inorder(Node node) {
    if (node == null) return;
    inorder(node.left);
    System.out.print(node.item + "->");
    inorder(node.right);
  }

  void preorder(Node node) {
    if (node == null) return;
    System.out.print(node.item + "->");
    preorder(node.left);
    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
4->2->3->1->8->
Preorder traversal 
1->2->4->3->8->
Postorder traversal 
4->3->2->8->1->
Footer Content | CrackEase
→
←