Reputation: 55
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
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