Simple binary tree insertion

[lost110]

Below is the code for BST. But what about a simple binary tree? If I want to do insertion of nodes from left to right without seeing whether its less or bigger then root node.
See this : https://ibb.co/TYwHV5P

void Insert(Node *& root, int data)
{
  if(root == nullptr)
  {
    Node * nn = new Node;
    root = nn;
  }
  else
  {
    if(data < root->data)
    { 
      Insert(root->left, data);
    }
    else
    {
      Insert(root->right, data);
    }
  }
}

[lost110]

The confusing thing is that after inserting the red color node, the temp will again start from the start and check whether right or left == NULL. But both are not NULL. How would it know that now I have to move to right part and insert it there.?

#include <iostream>
using namespace std;
struct abc
{
	abc *left;
	abc*right;
	int data;
};
abc *root = NULL;
void insert()
{
	abc *newnode = new abc;
	cout << "Enter data in node:" << endl;
	cin >> newnode->data;
	newnode->left = newnode->right = NULL;
	if (root == NULL)
	{
		root = newnode;
	}
	else
	{
		abc *temp = root;
		while (temp != NULL)
		{
			if (temp->left == NULL)
			{
				temp->left = newnode;
				break;
			}
			else if (temp->right == NULL)
			{
				temp->right = newnode;
				break;
			}
			else if

		}
	}


}

[lost110]

Anyone?

[Ganado]

Below is the code for BST. But what about a simple binary tree? If I want to do insertion of nodes from left to right without seeing whether its less or bigger then root node.

I do not know what this means. Like, you want an "unordered" binary tree? That defeats the whole purpose of a tree, unless you're actually making an unordered hash table in disguise, because if not, look-up is still O(N).

Re: second post,
When you do an insert, you should be updating the node you're looking at. So in your "else if" branch on line 35, you need to decide which branch (left or right) you want to travel down, either
temp = temp->left; or temp = temp->right;

The way to know which path to travel down is decided by an ordering (if the insert value is less than the parent node's value, travel left. If it's greater than, travel right.)

But it sounds like you're trying to avoid this for some odd reason, so I don't know what you're going for.

[jonnin]

agree: trees should have some sort of order. Many do not have a sorted order / BST, but they all share some ordering that lets you traverse to the leaves in a linear fashion while avoiding the unused branches. If it does not do that, you just have an inefficient unsorted vector that not only has pointer allocation slowness and pointer dereference slowness, it also is memory fragmented. It has no advantages or use case. If you had special hardware like CUDA or something with many, many processors, you can search in parallel down branches and recover your wall-clock time at the cost of hardware, and that may have merits for something but it seems 'off' for normal scenarios.

You mentioned RED, is this a RED/BLACK tree? Those have rules: they are a BST with additional rules. If this is what you are doing, you need to review that concept.

[coder777]

You need two loops: One outer for the level and one inner for the elements of that level.

You need also two vectors: One for the current level and one for the next level.

In the inner loop you fill the next level vector with the children (left/right) of the current level vector.
When you found the NULL you're done (break the outer loop by setting done = true).
if done == false (after the inner loop has finished) copy the next level vector to the current level vector and clear the next level vector. Otherwise break the outer loop.

[Ganado]

Ah, I never studied red-black trees really at all (only AVL trees).

One thing I thought of is that if lost110 wants O(log(n)) insert, but O(n) look-up, they could just randomly decide to go left or right during insert until a free child pointer is found. :)

[jonnin]

I almost never use trees, I prefer memory in blocks for most of what I do. If you had a hybrid tree that lives in an array, you could do some funky insert logic, even to the point of some sort of hashing under the hood. Could be fun, but to what practical purpose, I know not.

R/B trees balance on the fly, avoiding the 'balance()' method of normal BST. I don't remember how that actually works, just the name and purpose stuck. Its for when there isnt enough downtime to run a balance in the down-time between activity, like a real time system.

[lost110]

Thanks, everyone! So I'll stay on Bst!