Binary Tree Implementation in C++ - Learn DSA

Things to be discussed in this Article

  • Introduction (Previous Article)

  • Binary Tree (Previous Article)

    • Types of Binary Tree (Previous Article)

    • Traversals in a Binary Tree (Previous Article)

    • Applications (Previous Article)

  • Implementation of Binary Tree

  • Practice Problems

In the last article, we learnt about the basics of Binary Tree, the type of Binary trees, and the traversals which are possible in a binary tree. Now, we'll implement that using C++.

Implementation of Binary Tree

  • Representation of a Binary Tree Node

A node of a binary tree is represented by a structure containing a data part and two pointers to other structures of the same type.


C++ Implementation of Binary Tree


    #include <iostream>
    #include <stdlib.h>
    using namespace std;

    struct node
    {
        int value;
        struct node *left;
        struct node *right;
    };

    struct node *newNode(int value)
    {
        struct node *temp = (struct node *)malloc(sizeof(struct node));

        temp->value = value;
        temp->left = NULL;
        temp->right = NULL;

        return (temp);
    }

    void preOrder(struct node *t)
    {
        if (t != NULL)
        {
            cout << " " << t->value;
            preOrder(t->left);
            preOrder(t->right);
        }
    }
    void inOrder(struct node *t)
    {
        if (t != NULL)
        {
            inOrder(t->left);
            cout << " " << t->value;
            inOrder(t->right);
        }
    }
    void postOrder(struct node *t)
    {
        if (t != NULL)
        {
            postOrder(t->left);
            postOrder(t->right);
            cout << " " << t->value;
        }
    }

    int main()
    {
        struct node *root = newNode(1);

        root->left = newNode(2);
        root->right = newNode(3);

        root->left->left = newNode(4);

        cout << "The preorder traversal is: ";
        preOrder(root);
        cout << "\nThe inorder traversal is: ";
        inOrder(root);
        cout << "\nThe postorder traversal is: ";
        postOrder(root);
    }


Conclusion

In this article, we learnt about how to implement a Binary Tree in C++. It is actually very useful and easy to understand. This is one of the best places to start when understanding complex tree data structures. In the next article, we'll learn about Binary Search Trees which is a specific version of Binary Tree and it's related properties.


The Related Articles which you should read after this


If there is any error or you have any doubt in the article then do ask us through the comment section, we will be happy to help you.

If you think that this article has helped you to learn something then do share this with your friends.

Thank You for Reading.