Binary Tree Implementation in CPP

1. Introduction

A Binary Tree is a hierarchical data structure in which each node has at most two children, commonly referred to as the left and right child. Binary trees have a wide range of applications, including being used as the foundational structure for binary search trees, heaps, and more. In this post, we'll look at a basic implementation of a binary tree in C++.

2. Implementation Steps

1. Define a Node class that will represent each individual element (or node) in the binary tree. The class will contain data and pointers to its left and right children.

2. Create a BinaryTree class that will encapsulate the tree's behavior.

3. Implement methods to insert nodes (insert), traverse the tree in in-order (inOrderTraversal), and display the tree structure.

4. Demonstrate the usage of the BinaryTree class in a main function.

3. Implementation in C++ Programming

#include<iostream>
class Node {
public:
    int data;           // Data stored in the node
    Node* left;         // Pointer to the left child
    Node* right;        // Pointer to the right child
    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};
class BinaryTree {
private:
    Node* root;
    void inOrderTraversal(Node* node) {
        if (node == nullptr) return;
        inOrderTraversal(node->left);
        std::cout << node->data << " ";
        inOrderTraversal(node->right);
    }
public:
    BinaryTree() {
        root = nullptr;
    }
    void insert(int value) {
        if (root == nullptr) {
            root = new Node(value);
            return;
        }
        Node* currentNode = root;
        Node* parentNode = nullptr;
        while (currentNode != nullptr) {
            parentNode = currentNode;
            if (value < currentNode->data) {
                currentNode = currentNode->left;
            } else {
                currentNode = currentNode->right;
            }
        }
        if (value < parentNode->data) {
            parentNode->left = new Node(value);
        } else {
            parentNode->right = new Node(value);
        }
    }
    void displayInOrder() {
        std::cout << "In-Order Traversal: ";
        inOrderTraversal(root);
        std::cout << std::endl;
    }
};
int main() {
    BinaryTree bt;
    bt.insert(50);
    bt.insert(30);
    bt.insert(70);
    bt.insert(20);
    bt.insert(40);
    bt.insert(60);
    bt.insert(80);
    bt.displayInOrder();
    return 0;
}

Output:

In-Order Traversal: 20 30 40 50 60 70 80

Explanation:

1. Node class represents individual elements of the binary tree. Each node contains data and pointers to its left and right children.

2. BinaryTree class encompasses the behavior of the binary tree.

3. insert(int value): Inserts a new node with the given value into the tree by traversing down the tree to find the appropriate location based on value comparisons.

4. inOrderTraversal(Node* node): A private helper method that recursively traverses the tree in in-order (left, root, right) and prints each node's data.

5. displayInOrder(): Initiates the in-order traversal starting from the root.

6. main(): Demonstrates the usage of the binary tree by inserting nodes and displaying them using in-order traversal.