Build Binary Tree in C++ (Competitive Programming)

Let’s start our journey of learning a hierarchical data structure (BINARY TREE) in C++. We will start from very basic of creating a binary tree with the help of class and functions. In this tutorial, we will learn how to build binary tree in C++. Before that just grab some information about basics of Binary tree.

   Build Binary Tree in C++ (Competitive Programming)

Introduction

A binary tree comprises of parent nodes, or leaves, each of which stores data and also links to up to two other child nodes (leaves) which are visualized spatially as below the first node with one placed to the left and with one placed to the right.

Some of the important points of a binary tree are:-

  1. binary tree is made of nodes, where each node contains a left pointer (called the left subtree), a right pointer(called the right subtree), and a data element(data to be stored).
  2. The root pointer(node->root) points to the topmost node in the tree. A null pointer(NULL) represents a binary tree with no elements — >the empty tree.
  3. No order of data sorting is present in Binary tree.

Representation

It is generally represented as:

                              10
              	            /    \
	                   6      14
			  / \    /  \
		         5   8  11  18

The code is provided in C++ along with the essential information of the functions and classes. So, we created a class Node comprising of :Data to be stored, Left subtree pointer, Right subtree pointer, Parameterised constructor(node) along with two functions:-
1. Build tree
2. Print (taking the root node as an argument)

  • buildtree() function

The buildtree() inputs the value of data in variable d and root node is locally created with the data as d. The condition checks if the tree is empty (if empty return NULL) or not. The recursive call of function buildtree() is made on both left and right subtree of the binary tree and then root is returned.

  • print() function-

The print() function accepting root node is used to print the entire binary tree. If the tree is empty, no tree is printed. Else, the data of the root node is printed first followed by the recursive call of print function on both left and right subtree. A binary tree is build up and printed in main function by calling both functions.




Certainly the easiest code with optimized space and time complexity. This code is represented as Inorder traversal.

C++ Code – Inorder Traversal – Binary Tree

#include <iostream>
using namespace std;
class Node{
  public:
  int data;
  Node*left;
  Node*right;
  Node(int d){
    data=d;
    left=NULL;
    right=NULL;
  }
};
Node* buildtree(){
  int d;
  cin>>d;
  Node*root;
  if(d==-1){
    return NULL;
  }
  root=new Node(d);
  root->left=buildtree();
  root->right=buildtree();
  return root;
}
void print(Node*root){
  if(root==NULL){
    return;
  }
  cout<<root->data<<" ";
  print(root->left);
  print(root->right);
}
int main()
{
    Node*root=buildtree();	
    print(root);
  return 0;
}

Input:

3 4 -1 -1 5 -1 -1

Output:

3 4 5

You may also learn,


2 responses to “Build Binary Tree in C++ (Competitive Programming)”

  1. Shikha Srivastava says:

    For competitive programming which is more preferred using set in STL or using binary tree?

  2. Dolly Singh says:

    Well it all depends on the constraints within which you have to provide the solution.You can code by using sets in STL in optimized manner or can use binary trees with optimized functions to reduce complexity.It all depends on your knowledge of optimizing function use.Feel free to comment for further queries.

Leave a Reply

Your email address will not be published. Required fields are marked *