k1gabi
k1gabi

Reputation: 55

Question about implementation of binary search tree

I am trying to learn the basics of data algorithms in C# and when implementing the below binary search tree add in process I get stuck at understanding the following: when calling the tree1.add(20); method, on the first iteration of the while loop the current.Data has the value of 50 and on the second iteration of the loop the value of the same current.Data changes to 40. Why the value of the current.Data doesn't stuck at the value of 50 after the first iteration and what is the process by which the current.Data receives the value of 40?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarySearchTree
{
public class Node
{
    public int Data;
    public Node LeftChild;
    public Node RightChild;
}

public class BinarySearchTree
{
    public Node root;
    public BinarySearchTree()
    {
        root = null;
    }
    public void add(int data)
    {
        Node newNode = new Node();
        newNode.Data = data;
        if (root == null)
        {
            root = newNode;
        }
        else
        {
            Node current = root;
            Node parent;
            while (true)
            {
                parent = current;
                if (data < current.Data)
                {
                    current = current.LeftChild;
                    if (current == null)
                    {
                        parent.LeftChild = newNode;
                        break;
                    }
                }
                else
                {
                    current = current.RightChild;
                    if (current == null)
                    {
                        parent.RightChild = newNode;
                        break;
                    }
                }
            }
        }
    }
}


class Program
{
    static void Main(string[] args)
    {
        BinarySearchTree tree1 = new BinarySearchTree();
        tree1.add(50);
        tree1.add(40);
        tree1.add(60);
        tree1.add(20);
        tree1.add(45);
        tree1.add(55);
        tree1.add(65);

        Console.ReadLine();
    }
}
}

Upvotes: 2

Views: 51

Answers (1)

sagi
sagi

Reputation: 40481

The answer lays here:

while (true)
{
   parent = current;
   if (data < current.Data)
   {
      current = current.LeftChild; // THIS LINE
      if (current == null)
      {
         parent.LeftChild = newNode;
         break;
      }
   }

As you see, current is being revalued and now it is the left "child" of it self. After the first 3 add usages, the tree should look like this:

     50
    /  \
  40   60

So first iteration - current is 50, second iteration , it goes to the left(definition of a BST) and it becomes 40 . The next iteration current will contain NULL , (The left child of 40) and will be placed inside the BST.

Upvotes: 2

Related Questions