Singly Binary Tree Traversal: Data Structure

A Singly Binary Tree is a hierarchical data structure in which each node has at most two children, typically referred to as the left child and the right child. This structure enables efficient storage, organization, and retrieval of data in a way that resembles a branching hierarchy. To utilize a binary tree effectively, we need a systematic method to visit and process each node, this is where tree traversal comes into play.

In this data structure tutorial, you will learn about singly binary tree travel, different types of Singly Binary tree traversal, advantages and more on.  Build your coding foundation in just 21 days with our Free DSA Course and earn a certificate.

What is Singly Binary Tree Traversal?

A binary tree is a fundamental non-linear data structure where each node has at most two children: left and right. To effectively process or access all the nodes of a binary tree, we use tree traversal techniques.

A singly binary tree traversal refers to systematically visiting each node in a single binary tree (without considering multiple linked structures like threaded or doubly-linked trees). These traversal methods help in applications like expression parsing, file system management, searching, and data organization.

Types of Singly Binary Tree Traversal

There are two main categories of binary tree traversal:

1. Inorder (Left → Root → Right)
2. Preorder (Root → Left → Right)
3. Postorder (Left → Right → Root)

Breadth-First Traversal (BFS) – Visits nodes level by level (Level Order Traversal)

1. Inorder Traversal (DFS)

• In Binary Search Trees (BST), inorder traversal always produces nodes in sorted order.
• It is widely used when we want ordered data from a tree.
• In in-order traversal, the left child is visited first, followed by the node itself, and then the right child.
• Visit left subtree → root → right subtree.

Example Inorder Traversal (DFS)

#include 
#include 
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
// Create new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
// Inorder Traversal
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);          // Visit left
        printf("%d ", root->data);    // Visit root
        inorder(root->right);         // Visit 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: ");
    inorder(root);
    return 0;
}

Inorder Output: 4 → 2 → 5 → 1 → 3

2. Preorder Traversal (DFS)

• 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.
• Visit root → left subtree → right subtree.
• Commonly used to create a copy of a tree

Example Tree Output: 1 → 2 → 4 → 5 → 3.

#include 
#include 
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 = node->right = NULL;
    return node;
}
// Preorder Traversal
void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);   // Visit root
        preorder(root->left);        // Visit left
        preorder(root->right);       // Visit 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: ");
    preorder(root);
    return 0;
}

3. Postorder Traversal (DFS)

• 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.
• Visit left subtree → right subtree → root.
• Useful for deleting/freeing tree nodes or expression evaluation.

Example Output: 4 → 5 → 2 → 3 → 1

#include 
#include 
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 = node->right = NULL;
    return node;
}
// Postorder Traversal
void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);       // Visit left
        postorder(root->right);      // Visit right
        printf("%d ", root->data);   // Visit root
    }
}
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("Postorder Traversal: ");
    postorder(root);
    return 0;
}

4. Level Order Traversal (BFS)

• 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 - ....
• Visit nodes level by level starting from the root.
• Typically implemented with a queue.

Example Tree Output: 1 → 2 → 3 → 4 → 5

#include 
#include 
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 = node->right = NULL;
    return node;
}
// Calculate height of tree
int height(struct Node* node) {
    if (node == NULL) return 0;
    int lHeight = height(node->left);
    int rHeight = height(node->right);
    return (lHeight > rHeight ? lHeight : rHeight) + 1;
}
// Print nodes at a given level
void printLevel(struct Node* root, int level) {
    if (root == NULL) return;
    if (level == 1) printf("%d ", root->data);
    else if (level > 1) {
        printLevel(root->left, level - 1);
        printLevel(root->right, level - 1);
    }
}
// Level order traversal
void levelOrder(struct Node* root) {
    int h = height(root);
    for (int i = 1; i <= h; i++) {
        printLevel(root, i);
    }
}
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("Level Order Traversal: ");
    levelOrder(root);
    return 0;
}

Implementation of a Binary Tree in Different Programming Languages

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

    # Traverse preorder
    def traversePreOrder(self):
        print(self.val, end=' ')
        if self.left:
            self.left.traversePreOrder()
        if self.right:
            self.right.traversePreOrder()

    # Traverse inorder
    def traverseInOrder(self):
        if self.left:
            self.left.traverseInOrder()
        print(self.val, end=' ')
        if self.right:
            self.right.traverseInOrder()

    # Traverse postorder
    def traversePostOrder(self):
        if self.left:
            self.left.traversePostOrder()
        if self.right:
            self.right.traversePostOrder()
        print(self.val, end=' ')


root = Node(5)

root.left = Node(6)
root.right = Node(7)

root.left.left = Node(8)

print("Preorder Traversal: ", end="")
root.traversePreOrder()
print("\nInorder Traversal: ", end="")
root.traverseInOrder()
print("\nPostorder Traversal: ", end="")
root.traversePostOrder()
    

// Node creation
class Node {
  int key;
  Node left, right;

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

class BinaryTree {
  Node root;

  BinaryTree(int key) {
  root = new Node(key);
  }

  BinaryTree() {
  root = null;
  }

  // Traverse Inorder
  public void traverseInOrder(Node node) {
  if (node != null) {
    traverseInOrder(node.left);
    System.out.print(" " + node.key);
    traverseInOrder(node.right);
  }
  }

  // Traverse Postorder
  public void traversePostOrder(Node node) {
  if (node != null) {
    traversePostOrder(node.left);
    traversePostOrder(node.right);
    System.out.print(" " + node.key);
  }
  }

  // Traverse Preorder
  public void traversePreOrder(Node node) {
  if (node != null) {
    System.out.print(" " + node.key);
    traversePreOrder(node.left);
    traversePreOrder(node.right);
  }
  }

  public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();

  tree.root = new Node(5);
  tree.root.left = new Node(6);
  tree.root.right = new Node(7);
  tree.root.left.left = new Node(8);

  System.out.print("Preorder Traversal: ");
  tree.traversePreOrder(tree.root);
  System.out.print("\nInorder Traversal: ");
  tree.traverseInOrder(tree.root);
  System.out.print("\nPostorder Traversal: ");
  tree.traversePostOrder(tree.root);
  }
}
    

#include <stdlib.h>
#include <iostream>
using namespace std;

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

// New node creation
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);
}

// Traverse Preorder
void traversePreOrder(struct node *temp) {
  if (temp != NULL) {
    cout << " " << temp->data;
    traversePreOrder(temp->left);
    traversePreOrder(temp->right);
  }
}

// Traverse Inorder
void traverseInOrder(struct node *temp) {
  if (temp != NULL) {
    traverseInOrder(temp->left);
    cout << " " << temp->data;
    traverseInOrder(temp->right);
  }
}

// Traverse Postorder
void traversePostOrder(struct node *temp) {
  if (temp != NULL) {
    traversePostOrder(temp->left);
    traversePostOrder(temp->right);
    cout << " " << temp->data;
  }
}

int main() {
  struct node *root = newNode(5);
  root->left = newNode(6);
  root->right = newNode(7);
  root->left->left = newNode(8);

  cout << "preorder traversal: ";
  traversePreOrder(root);
  cout << "\nInorder traversal: ";
  traverseInOrder(root);
  cout << "\nPostorder traversal: ";
  traversePostOrder(root);
}
    

Output

Preorder traversal:  5 6 8 7
Inorder traversal:  8 6 5 7
Postorder traversal:  8 6 7 5

Advantages of Tree Traversal

1. Systematic Processing of Nodes

• Tree traversal ensures that every node in a tree is visited exactly once in a specific order (Inorder, Preorder, Postorder, or Level Order).
• This systematic approach avoids missing any data or visiting a node multiple times.
• Example: In a binary search tree (BST), inorder traversal retrieves all elements in sorted order.

2. Supports Searching, Sorting, and Data Manipulation

• Traversals help implement efficient search algorithms in trees like BST, AVL, and B-trees.
• Sorting can be achieved using inorder traversal (O(n) after tree creation).
• Example: Searching for a student’s roll number in a student database system stored as a BST

3. Backbone of Expression Trees, Parsers, and Compilers

• Traversals play a key role in converting and evaluating arithmetic expressions.
• Preorder traversal generates prefix expressions, inorder gives infix expressions, and postorder evaluates postfix expressions.
• Example: Expression tree for (A + B) * (C - D) uses postorder traversal to evaluate correctly.

4. Efficient Hierarchical Data Storage

• Many data formats (XML, JSON, HTML DOM) naturally represent data as a tree.
• Traversals make it possible to parse, search, and modify these structures efficiently.
• Example: Web browsers traverse the DOM tree to render HTML elements correctly.

Real-World Applications of Tree Traversal

1. Expression Evaluation:

• Expression trees use different traversals to parse and evaluate arithmetic operations.
• Postorder is often used for evaluation since operands are processed before operators.
• Example: Compilers use postorder traversal for generating machine code instructions.

2. File System Navigation (Operating Systems)

• The hierarchical file structure (folders inside folders) is a tree structure.
• OS uses preorder traversal to list directories and postorder traversal for deleting folders.
• Example: dir /s in Windows or ls -R in Linux uses recursive tree traversal.

3. Database Indexing (B-Trees, BSTs, AVL Trees)

• In databases, indexing structures like B-Trees and B+ Trees use traversals for efficient search, range queries, and insertion.
• Example: SQL queries like SELECT * FROM students WHERE marks BETWEEN 50 AND 80; use inorder traversal of a B-Tree index.

4. Networking (Routing Tables & Packet Forwarding)

• Network routing tables can be stored as a trie (prefix tree) or binary tree.
• Traversals allow efficient lookup for IP addresses and routes.
• Example: Routers use trie traversal for longest prefix matching in IP routing.

5. Artificial Intelligence & Game Development

• Traversals are used in decision trees, minimax trees, and search trees for AI decision-making.
• Level order traversal (BFS) is often used in shortest path finding (like A* or BFS in graphs).
• Example: In chess AI, minimax algorithm with preorder/postorder traversals helps evaluate moves.

Conclusion

Singly binary tree traversal forms the foundation of working with hierarchical data structures. Whether using inorder, preorder, postorder, or level order, each method serves a distinct purpose in programming, system design, and real-world applications. Mastering these techniques strengthens problem-solving skills and prepares you for technical interviews and advanced algorithms.

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE