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

user_13757087 0
Viewed 1102

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.

binary-tree c#
2 Answers

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:

user_71675720

Depends on your usecase how you want to define indexing if its indexed while its making the binary tree or the in order traversal index . Here is an example from python code but the concept will remain the same.

 class BinaryTree(Counter):
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

    # To print default binary Tree
    def __str__(self):
        return str(self.data)+str(self.in_order_traversal())    
    
    def add_child(self,data):
        if self.data == data:
            return
        if self.data<data:
            if self.right:
                return self.right.add_child(data)
            else:
                self.right = BinaryTree(data)
                self.index += 1
        if self.data > data:
            if self.left:
                return self.left.add_child(data)            
            else:
                self.left = BinaryTree(data)
                self.index += 1

    
    def in_order_traversal(self):
        elements = []
        if self.left:
            elements += self.left.in_order_traversal()
        elements.append(self.data)
        if self.right:
            elements += self.right.in_order_traversal()
        return elements

    # This the function for index.
     def index_of(self,val):
        elements = self.in_order_traversal()
        if val in elements:
            return elements.index(val)
        return False
                       
   
 def build_tree(elements):
    start = 0 
    end = len(elements) - 1
    mid = start + (end-start)//2
    root = BinaryTree(elements[mid])
    for e in elements:
        root.add_child(e)
    return root 
 elements = [20,10,2,5,100,50,30]
 my_tree = build_tree(elements)
 print(my_tree)
 print(my_tree.in_order_traversal())
 print(my_tree.search(5))

If in order traversal its simple just call inorder traversal and inside inorder traversal store the elements in a list for all the node in correct order with recursive calling. After that inside index function check if the val exist then get the index

user_192133120
Related