Clash Royale CLAN TAG#URR8PPP

Why do we need Parent Node in Binary Search Tree - C#

I have only started learning Data Structures so please bear my stupidity, I am trying to develop my own version of BST, I can't get why there is a need of a parent Node? Shouldn't this work just fine.

class BST

private Node root;

public BST()

root = null;


public void insert(int value)

Node temp = new Node();
temp.value = value;

if (root == null)

root = temp;
return;


Node current = root;

while (current != null)

if (value <= current.value)

current = current.lc;

else

current = current.rc;



current = temp;



class Node

public Node lc;
public int value;
public Node rc;



There is definitely something that I am missing and I can't grasp or get what it is, when current is null, we are already onto where we need to insert the node, why then do we need a parent node.

current = temp;

temp

parent.lc

parent.rc

3 Answers
3

This may work

class BST

private Node root = null;

public void insert(int value)

Node temp = new Node value = value ;

if (root == null)

root = temp;
return;


var current = root;

while (current != null)

if (value <= current.value)

if (current.lc == null)

current.lc = temp;
break;

current = current.lc;

else

if (current.rc == null)

current.rc = temp;
break;

current = current.rc;






class Node

public Node lc;
public int value;
public Node rc;



You are mixing variables with references to fields/variables. The current variable holds the value of the lc or rc field (the copy of the field). Setting the variable does not set the corresponding field, just assigns another value to the variable.

current

lc

rc

Hence the line

current = temp;


does not insert the node in the BST.

What you are trying to do is possible with C#7.0 introduced ref locals and returns and C#7.3 introduced improvements which allow to reassign ref local variables.

The ref local variables are exactly what is your intention - they contain the location (reference, address) of some other field / variable. So the following works (requires C#7.3!):

public void insert(int value)

ref Node nodeRef = ref root;
while (nodeRef != null)

if (value <= nodeRef.value)
nodeRef = ref nodeRef.lc;
else
nodeRef = ref nodeRef.rc;

nodeRef = new Node value = value ;



Note the usage of ref keyword. You use nodeRef = ref … to assign a reference (address) of a variable (in this case either root or some node lc or rc field), and nodeRef = … to assign a value to the variable pointed by the nodeRef.

ref

nodeRef = ref …

root

lc

rc

nodeRef = …

nodeRef

You are setting "null" to some instance.

In your while loop current eventually becomes null, and you are missing the connection between nodes.

To fix this issue you should keep the last node of your tree.

You can try the below :

class BST

private Node root;

public BST()

root = null;


public void insert(int value)

root = insert(root, value);


private Node insert(Node node, int value)
// if the given node is null it should be new node
if (node == null)
node = new Node();
node.value = value;
return node;


if (value < node.value)
// if our value lower then current value then we will insert left node recursively
node.lc = insert(node.lc, value);
else if (value > node.value)
// if our value higher then current value then we will insert right node recursively
node.rc = insert(node.rc, value);

return node;


public void print()
print(root);


private void print(Node node)
if (node != null)
print(node.lc);
Console.WriteLine(node.value);
print(node.rc);

return;




public static void main(String args)

BST bst = new BST();

bst.insert(5);
bst.insert(25);
bst.insert(15);
bst.insert(4);

bst.print();



The output is :

4
5
15
25


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.