How to construct a Binary tree in C/ C ++

Constructing a binary tree in C/C++ typically involves defining a structure for the binary tree node and implementing functions to create new nodes, insert nodes, and traverse the tree. The following sections detail how to construct a simple binary tree in C/C++.

1. Defining the Binary Tree Node Structure

First, define a structure for the binary tree node TreeNode, which includes an integer data field data and two pointers left and right pointing to the left and right subtrees:

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

    // Constructor
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

2. Creating New Nodes

Creating new nodes can be achieved by directly using the TreeNode constructor, as defined earlier.

3. Inserting Nodes

To insert nodes, compare the value to be inserted with the current node's value and recursively place the new value in the left or right subtree based on the comparison:

cpp
TreeNode* insertTreeNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val < root->data) {
        root->left = insertTreeNode(root->left, val);
    } else if (val > root->data) {
        root->right = insertTreeNode(root->right, val);
    }

    return root;
}

4. Traversing the Binary Tree

Binary tree traversal typically includes pre-order, in-order, and post-order traversals. For example, in an in-order traversal, recursively traverse the left subtree, visit the root node, and then recursively traverse the right subtree:

cpp
void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

Example Code

Combining the above, a complete example code is as follows:

cpp
#include <iostream>

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

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

TreeNode* insertTreeNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val < root->data) {
        root->left = insertTreeNode(root->left, val);
    } else if (val > root->data) {
        root->right = insertTreeNode(root->right, val);
    }

    return root;
}

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    TreeNode* root = nullptr;
    root = insertTreeNode(root, 8);
    insertTreeNode(root, 3);
    insertTreeNode(root, 10);
    insertTreeNode(root, 1);
    insertTreeNode(root, 6);
    insertTreeNode(root, 14);

    std::cout << "Inorder traversal of binary tree: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

This code first constructs a binary tree, inserts several nodes, and uses in-order traversal to output them. This represents the fundamental approach for building and manipulating binary trees.