binary-tree binary-search-tree insertion

Binary Tree Structure

I am trying to solve this problem where a new joining peer will be given an index [0,1,2, ... n-1] based on how many peer objects already exist (e.g. 8 exist -> new peer will get index 8).

I want to add these peer objects into a binary tree based on their index. For example, peer 0 joins and it will be the root, then peer 1 & peer 2 will be peer 0's left and right children.

I only need the binary tree to follow the rule that it should have two children.

Here's an example:

My problem is that I am unsure of how to actually do this insertion to keep the 2 children rule. At first I assumed a normal BST insertion rule would work, but once I actually coded that up, I realized the problem of the pivot/key - I am inserting based on the index. Everything would just become a right child

I am really stuck on this but I think the solution should be a trivial one that I am just unable to see. Any advice?

Edit: Thank you for the help! I think I figured out something that will meet my needs so I'll leave it here. I will have an implicit binary tree structure. Peers that join up will get put into a priority queue based on their index. This will signify whether they can have children assigned to them & a peer will be removed from this queue once it has 2 children

Solution

A few things that you want to consider:

Why do you want a BST?

BSTs are, as the name implies, primarily for searching. But if you are assigning every new user that joins a unique identifier, then you don't need to use a BST to search for them, because you can access them from an array by index.

A BST would be more useful if, say, each user played a game and earned a particular score. To organize the users in a data structure that would render them easily searchable/organizable by score, you might insert a player into the BST with their score as the key when they finished the game. But for unique identifiers like this, there is no reason fo use a BST. In fact, the data structure that you show there is not a BST. The BST would look like this:

Is another data structure more appropriate?

If you have gotten a better sense of why a BST is not a useful structure for organizing user IDs, then you should next think about what is is you were actually trying to do. If you were just trying to store all the users in a data structure, a list (array) is totally fine, where the index of the list corresponds to the user id.

If you are instead looking to add some sort of grouping to these users, consider using a hash table. For example, if you wanted to be able to look up a user's friends, you would create a hash table where a user id (key) maps to a list of friends' user ids (value).

Hopefully this has been helpful. If there is any more that I can do to help or if I have not fully understood what you are trying to accomplish, just let me know

UPDATE

So based on the comments above, it seems your confusion is on the distinction between a binary tree and a BST. A binary tree is any tree where each node has <= 2 children, whereas a Binary search tree imposes additional constraints on the values of the nodes' keys. The binary tree structure is what you want, but you don't need it for searching, nor do you want to compare those values.