C++ tutorial: structure-Add a new node

C++ structure-add node to Binary Search Tree

Step 2: add a new node to the tree

To add a new node to the tree, we need a recursive process to locate the appropriate location of the tree. The process starts from the root node. If the tree is empty, the new node will become the root node. If the tree is not empty, the new node will be checked against the parent node. If it is less than the parent node, the process will look for the proper location in the left side, otherwise, it looks in the right side. If the parent node is equal to the new node, it will do nothing. This process continues recursively until it finds the proper location.

Add a new node to the tree  

//insert a new node
ListElem *Insert (ListElem **T,int Tar)


  ListElem *item;//new element to be inserted
  item=(ListElem *)malloc(sizeof(ListElem)); //allocate space
  if(!item) {printf("Memory problem..."); exit(100);}

  else {

  if(Tar<(*T)->data) (*T)->pLeft=Insert(&(*T)->pLeft, Tar);
  else if(Tar>(*T)->data) (*T)->pRight=Insert(&(*T)->pRight,Tar);


return *T;


You should note that the base of the recursive process to add the new node is NULL value. This means that process will add the new node to be a child node of a node that has one or zero child. Another important thing to consider is passing the T parameter by reference. The T is passed by reference to make sure the entire tree can be achieved or new node is added to the tree when the adding node process stops.


This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.