Binary Tree Traversals in c++

Binary Tree Traversals in C++

Binary tree is a widely used data structure in computer science. It is a tree data structure in which each node can have at most two children, which are referred to as left child and right child. A binary tree is often used to implement other data structures like linked lists, stacks, queues, etc. In this article, we will discuss the different ways to traverse a binary tree in C++.

The three most common ways to traverse a binary tree are:

1. In-order traversal
2. Pre-order traversal
3. Post-order traversal

Before diving into the traversal algorithms, let's first discuss the basic structure of a binary tree node in C++.

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

In this structure, data is the value stored in the node, left is a pointer to the left child, and right is a pointer to the right child.

1. In-order traversal:

In-order traversal is a depth-first traversal method where the left subtree is visited first, then the root, and finally the right subtree. This can be implemented using recursion or using a stack.

// Recursive In-Order Traversal
 
void InOrder(Node* root) {
 if (root == NULL) return;
 InOrder(root->left);
 cout << root->data << " ";
 InOrder(root->right); 
}

// Iterative In-Order Traversal 
 void InOrder(Node* root) { 
 stack<Node*> s;
 Node* curr = root;
     
while (curr != NULL || !s.empty()) { 
 while (curr !=  NULL) {
 s.push(curr); 
 curr = curr->left; 
 } 
curr = s.top();
 s.pop();
 cout << curr->data << " ";
 curr = curr->right;
 } 
}

2. Pre-order traversal:

Pre-order traversal is a depth-first traversal method where the root is visited first, then the left subtree, and finally the right subtree. This can also be implemented using recursion or using a stack.

// Recursive Pre-Order Traversal 
 void PreOrder(Node* root) { 
 if (root == NULL) return; 
 cout << root->data << " ";
 PreOrder(root->left);
 PreOrder(root->right);
 }

// Iterative Pre-Order Traversal
 
void PreOrder(Node* root) { 
stack<Node*> s;
 s.push(root);
 while (!s.empty()) {
 Node* curr = s.top();
 s.pop();
 cout << curr->data << " "; 
 if (curr->right) s.push(curr->right);
         
if (curr->left) s.push(curr->left);
    }
}

3. Post-order traversal:

4. -first traversal method where the left subtree is visited first, then the right subtree, and finally the root. This can also be implemented using recursion or using a stack.

   // Recursive Post-Order Traversal 
   void PostOrder(Node* root) {
    if (root == NULL) return;
    PostOrder(root->left);
    PostOrder(root->right); 
    cout << root->data << " ";
   }
   

   // Iterative Post-Order Traversal
    
   void PostOrder(Node* root) { 
    stack<Node*> s1, s2;
       s1.push(root); 
    while (!s1.empty()) {
           Node* curr = s1.top();
    s1.pop();
           s2.push(curr);
    if (curr->left) s1.push(curr->left);
    if (curr->right) s1.push(curr->right);
    }
    while (!s2.empty()) {
           Node* curr = s2.top();
    s2.pop();
    cout << curr->data << " "; 
    }
   }
   

   In conclusion, binary tree traversals are a fundamental concept in computer science and are widely used in many applications. By understanding the different ways to traverse a binary tree, you can choose the appropriate method for your specific use case. Whether you prefer to use recursion or a stack, the key is to understand the order of visiting the nodes in the tree.