Easiest way to get the index of a node in a Binary Tree c#

Question

I want to get the index of all the nodes in a bst. The code i am using to insert the values and search a node is

public class BTS
{
    public class Node
    {
        public int value;
        public Node Left;
        public Node Right;
    }


    public Node Insert(Node nod,int value)
    {
        if (nod == null)
        {
            nod = new Node();
            nod.value = value;
        }
        else if(value < nod.value)
        {
            nod.Left = Insert(nod.Left, value);
        }
        else if(value > nod.value)
        {
            nod.Right = Insert(nod.Right, value);
        }
        return nod;
    }

    public string FindNode(Node node, int s)
    {
        string Output = "";
        if (node == null)
            return Output = "not found";
        else if (s.CompareTo(node.value) < 0)
            return FindNode(node.Left, s);
        else if (s.CompareTo(node.value) > 0)
            return FindNode(node.Right, s);

        return Output = "found";
    }
    static void Main()
    {
        Node N = null;
        BTS bs = new BTS();
        N = bs.Insert(N, 10);
        N = bs.Insert(N, 9);
        N = bs.Insert(N, 8);
        N = bs.Insert(N, 11);
        N = bs.Insert(N, 12);
        bs.FindNode(N,9);
    }
}

the above code gives me the value as true if the node 9 is present. But i want to get the index of the node just like how we get index for an array.

Thank you in advance.

What have you tried? How did you approach this looking for index? What was the problem during resolving that? — Tatranskymedved, Dec 15 '20 at 11:59
you want to access node like bs[2] or you wanna know 'index' of node with value 2 ? — Pribina, Dec 15 '20 at 12:03
And second question is, what exactly index mean? If you google for `binary tree image`, what index should be returned for those elements in the middle? This is where you must instert your logic and decide how to search through that tree. If go from bottomToTop or topToBottom. If you count child nodes or you will consider how far away it is. If you will introduce your own property and set it to elements incrementaly just to have some number. There are many possibilities, you should start with trying some. — Tatranskymedved, Dec 15 '20 at 12:03
I could not find any answer related to that in c# or get it to implement, that is the reason i am asking in the forum @Tatranskymedved — Is'haq, Dec 15 '20 at 12:04
@Pribina exactly. i want a bs[2] approach just like we access all the array elements in a loop. For now top to bottom approach will work. I will work for the bottom to top approach. — Is'haq, Dec 15 '20 at 12:05
@GarnimittaIshaq the important counter-question is - What index mean? Which number represent which element? Because in array the elements are going continuously one after other. But binary tree is a *tree* and it is not linear. — Tatranskymedved, Dec 15 '20 at 12:06
@Tatranskymedved https://media.geeksforgeeks.org/wp-content/cdn-uploads/BITUpdate12.png in this image i would like to get the index of the node 2 which is 5. Hope i am able to make you understand my problem — Is'haq, Dec 15 '20 at 12:11
@GarnimittaIshaq you have multiple options here https://stackoverflow.com/questions/2675756/efficient-array-storage-for-binary-tree — Pribina, Dec 15 '20 at 12:14
@Pribina but that does not look like top to bottom approach. can you please help me with the code in c# where i can loop through all the nodes and get all the indexes — Is'haq, Dec 15 '20 at 12:19

Tatranskymedved · Accepted Answer · 2020-12-15T12:35:49.470

I will try to provide you the answer for this. At the beginning you have to separate this task to several subtasks:

How will I index each element?
- OP provided answer to that in the image in comments
How will I hold the index of each element?
- Probably on each element I add variable
- We can have some Dictionary<Node,int>
How am I going to assign the index?
- During element add
  - Insert that to the variable
  - or Insert that to the dictionary
- Once I need it, I will recalculate the indexes
  - Update all variables of all items
  - Update all items in the dictionary

Answer in theory: Both of the approaches however requires to add Node and recalculate all the indexes after. You basically need to create method that go through each element in the tree, from lowest value to the top most value and save its index somewhere.

We can borrow answer for iterating tree there:

Easiest way to get the index of a node in a Binary Tree c#

1 Answers1