# Understanding Binary Trees in C++

Binary Trees are one of the most fundamental data structures in computer science. They are the building block for more complex tree-based structures like Binary Search Trees, AVL Trees, and Red-Black Trees.

In this blog, we’ll explore a simple implementation of a Binary Tree in C++ and discuss the **in-order traversal** technique for visiting all the nodes systematically.

## What is a Binary Tree?

A Binary Tree is a hierarchical data structure in which:

1. Each node has at most two children: a left child and a right child.
    
2. Nodes are connected via edges.
    

A **Binary Tree** can be used for various applications, such as expression parsing, sorting, and search algorithms.

## Code Walkthrough

Here is the basic Binary Tree implementation code with in-order traversal in C++.

1. **Include Libraries and Define the Node Structure**
    
    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef struct Node Node;
    
    struct Node{
        int data;
        Node *left, *right;
    };
    ```
    
    #### **Explanation:**
    
    * **Libraries:**
        
        * `#include <bits/stdc++.h>` Includes all necessary standard libraries in C++.
            
    * **Node Structure:**
        
        * Each `Node` Contains:
            
            * `data`: Holds the value of the node.
                
            * `left` and `right`: Pointers to the left and right child nodes, respectively.
                
2. **Creating a New Node**
    
    ```cpp
    Node* newNode(int data){
        Node* node = (Node*)malloc(sizeof(Node));
        node->data = data;
        node->left = node->right = NULL;
        return node;
    }
    ```
    
    #### **Explanation:**
    
    * **Memory Allocation:**
        
        * The `malloc` function dynamically allocates memory for a new node.
            
    * **Node Initialization:**
        
        * `data` Is set to the provided value.
            
        * `left` and `right` pointers are initialized to `NULL`, indicating no children initially.
            
3. **In-Order Traversal**
    
    ```cpp
    void inOrder(Node* root){
        if(root){
            inOrder(root->left);
            cout << root->data << " ";
            inOrder(root->right);
        }
    }
    ```
    
    #### **What is In-Order Traversal?**
    
    * **Order:** Left → Root → Right
        
    * **Process:**
        
        * Recursively visit the left subtree.
            
        * Print `data` of the current node.
            
        * Recursively visit the right subtree.
            
    * **Output:** Produces the tree's elements in a sorted sequence if the binary tree is structured like a Binary Search Tree (BST).
        
4. **Main Function**
    
    ```cpp
    int main(){
        Node *root = NULL; 
        root = newNode(50);
        root->left = newNode(30);
        root->left->left = newNode(20);
        root->left->right = newNode(40);
        root->right = newNode(70);
        root->right->left = newNode(60);
        root->right->right = newNode(80);
        inOrder(root);
        return 0;
    }
    ```
    
    #### **Steps:**
    
    1. **Initialize Root Node:**
        
        * The tree is initialized with `root = NULL` and assigned a value using `newNode(50)`.
            
    2. **Construct the Tree:**
        
        * The following tree structure is created manually:
            
            ```bash
                     50
                   /    \
                 30      70
                /  \    /  \
              20   40  60   80
            ```
            
    3. **Perform In-Order Traversal:**
        
        * The `inOrder()` function is called with the root node, printing the tree’s elements in sorted order.
            

## Output

When the program is executed, the in-order traversal outputs the following sequence:

```bash
20 30 40 50 60 70 80
```

This confirms the left-to-right traversal of the binary tree.

## Advantages of Binary Trees

1. **Hierarchical Structure:**
    
    * Efficiently organizes data for searching, insertion, and deletion.
        
2. **In-Order Traversal:**
    
    * Provides a natural way to retrieve elements in sorted order.
        
3. **Flexibility:**
    
    * Binary Trees can be extended into specialized trees like BSTs, AVL Trees, and Heaps.
        

## Applications of Binary Trees

* **Search Trees:** Store and retrieve data efficiently.
    
* **Expression Trees:** Parse mathematical expressions.
    
* **Heap Trees:** Implement priority queues.
    
* **File Systems:** Organize hierarchical file structures.
    

## Conclusion

This implementation demonstrates the fundamentals of Binary Trees and their traversal using an in-order technique. While this example is static, you can extend it to dynamically build trees from user input or data arrays.

Understanding the basics of Binary Trees sets the foundation for learning more advanced tree-based data structures and algorithms.

Happy Coding! 😊

## **References**

1. Find the code for the above explanation [**here**](https://github.com/tanaytoshniwal/Data-Structures-Algorithms/blob/master/Data%20Structures/BinaryTree/Tree.cpp).