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

    #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

    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

    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

    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:

                   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:

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.