Trees and Tree Traversals

Trees and Tree Traversals

A tree is a hierarchical data structure that represents a collection of nodes, where one node is designated as the root, and the rest are connected via edges. Trees are widely used in scenarios like organizing data hierarchically (e.g., file systems) and implementing various algorithms efficiently (e.g., searching and sorting).

Basic Terms in Trees

1. Node: An element in the tree.
2. Root: The topmost node in the tree.
3. Parent and Child: A node connected above another is the parent, and the one below is the child.
4. Edge: The connection between two nodes.
5. Leaf Node: A node with no children.
6. Height of a Tree: The length of the longest path from the root to a leaf.
7. Depth of a Node: The distance from the root to that node.

Types of Trees

1. Binary Tree: Each node has at most two children (left and right).
2. Binary Search Tree (BST): A binary tree where:
   • Left subtree contains nodes with values smaller than the parent.
   • Right subtree contains nodes with values larger than the parent.
3. Balanced Tree: The height difference between the left and right subtrees of any node is minimal (e.g., AVL Tree).
4. Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
5. Full Binary Tree: Every node has either 0 or 2 children.
6. N-ary Tree: A tree where each node can have at most N children.

Tree Traversals

Traversal refers to visiting each node in the tree in a specific order. There are two primary types:

1. Depth-First Traversal (DFS)
2. Breadth-First Traversal (BFS)

1. Depth-First Traversal (DFS)

• DFS explores as far as possible along each branch before backtracking.
• Types of DFS traversals:

  1. Inorder Traversal (Left → Root → Right):

     • Used for Binary Search Trees to get sorted order.
     • Algorithm:
       1. Visit the left subtree.
       2. Visit the root node.
       3. Visit the right subtree.

     C++ Implementation:

     void inorder(TreeNode* root) {
         if (root == nullptr) return;
         inorder(root->left);         // Traverse left subtree
         cout << root->data << " ";  // Visit root
         inorder(root->right);        // Traverse right subtree
     }
     

  2. Preorder Traversal (Root → Left → Right):

     • Useful for copying trees or expressions.
     • Algorithm:
       1. Visit the root node.
       2. Visit the left subtree.
       3. Visit the right subtree.

     C++ Implementation:

     void preorder(TreeNode* root) {
         if (root == nullptr) return;
         cout << root->data << " ";  // Visit root
         preorder(root->left);       // Traverse left subtree
         preorder(root->right);      // Traverse right subtree
     }
     

  3. Postorder Traversal (Left → Right → Root):

     • Used for deleting or evaluating expression trees.
     • Algorithm:
       1. Visit the left subtree.
       2. Visit the right subtree.
       3. Visit the root node.

     C++ Implementation:

     void postorder(TreeNode* root) {
         if (root == nullptr) return;
         postorder(root->left);       // Traverse left subtree
         postorder(root->right);      // Traverse right subtree
         cout << root->data << " ";  // Visit root
     }
     

2. Breadth-First Traversal (BFS)

• BFS explores all nodes at the present depth level before moving to the next level. It is also called Level-Order Traversal.

Algorithm:

1. Use a queue to keep track of nodes at each level.
2. Start with the root and enqueue it.
3. While the queue is not empty:
   • Dequeue a node.
   • Process the node.
   • Enqueue its children (left and right).

C++ Implementation:

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

void levelOrder(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        cout << current->data << " ";

        if (current->left) q.push(current->left);
        if (current->right) q.push(current->right);
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "Level-Order Traversal: ";
    levelOrder(root);
    return 0;
}

Comparison of DFS and BFS

Example Tree:

Let’s consider this tree:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

DFS Traversals:

• Inorder: 4 2 5 1 6 3 7
• Preorder: 1 2 4 5 3 6 7
• Postorder: 4 5 2 6 7 3 1

BFS Traversal:

• Level Order: 1 2 3 4 5 6 7

Real-World Applications

1. Inorder:
   • Used in Binary Search Trees for retrieving elements in sorted order.
2. Preorder:
   • Used to create a copy of a tree or serialize it.
3. Postorder:
   • Used in evaluating or deleting expression trees.
4. Level Order:
   • Used in shortest path problems and breadth-based exploration.

This summary should help you understand tree structures and traversal techniques in an intuitive and detailed way! 😊