Thursday, 15 January 2015

Explain inserting the data into the Binary Tree in C++ with code examples

How to Insert the data into the Binary Tree in Cpp:

Here we are going to learn how to insert the new node into the binary tree.
I hope that you were remembered the previous post about the binary trees and the syntax of the binary tree. What is the binary tree? What is the structure of the binary tree and so on.

You can find more information on Binary Trees here.

InsertNewNode() – This function helps us to understand how to insert a new node with the given number into the tree in the in the correct place. The InsertNewNode() code modifies the tree structure.

The InsertNewNode() returns the new tree pointer to use to its caller. Calling InsertNewNode() with the number 4 on this tree.

Newly Inserted Node

The solution shown here introduces a CreateNewNode() helper function that builds a single node.
CreateNewNode () is the helper function that allocates a new node with the given data and NULL left and right pointers.

struct stNode* CreateNewNode(int data) 
struct stNode* pcstNode = new(struct stNode); // "new" is like "malloc"
pcstNode ->data = data;
pcstNode ->left = NULL;
ocstNode->right = NULL;

Give a binary search tree and a number, inserts a new node with the given number in the correct place in the tree.
Returns the new root pointer which the caller should then use.

struct stNode* InsertNewNode(struct stNode* pstNode, int iData)
//Verify if the tree is empty, return a new, single pstNode
if (pstNode == NULL) {

else {

    // Otherwise, recursively down the tree and insert the new node at the valid location
  if (iData <= pstNode->iData)
    { pstNode->left = InsertNewNode(pstNode->left, iData); }
    pstNode->right = InsertNewNode(pstNode->right, iData);
The shape of a binary tree depends very much on the order that the nodes are inserted.
The nodes are inserted in increasing order (1, 2, 3, 4), the tree nodes just grow to the right leading to a linked list shape where all the left pointers are NULL.

A similar thing happens if the nodes are inserted in decreasing order (4, 3, 2, 1). The linked list shape defeats the lg(N) performance.

We will not address that issue here, instead focusing on pointers and recursion.
Post your comments /reviews and suggestions if any…

1 comment:

edwrede_ZA said...

Hi there Pavuluri.

I actually came across this site after seeing a question you posted on the QUEFORUM regarding XMLVEND.

I'm having the exact same issue you had: "Failed to get reference to SOAP engine".

Please could you tell me how you fixed this?

Keep well and thank you!