Recursive function implementation for Binary search tree

Question

I am trying to implement a basic Binary search tree.

I was able to create a Node and I have problems with the AddNode() function. It is supposed to add a new node to the existing tree but it replaces it.

Any ideas what should be done in the AddNode() function ?

class Node
{
    public int value { get; set; }

    public Node left { get; set; }

    public Node right { get; set; }

    public Node(int i)
    {
        this.value = i;
        this.left = null;
        this.right = null;
    }

}

class Tree
{
    public Node root { get; set; }

    public Tree(Node n)
    {
        root = n;
    }

    public void AddNode(int valueToBeInserted)
    {
        if (this.root == null)
        {
            this.root = new Node(valueToBeInserted); 
            // problem here : existing tree is destroyed. 
            // a new one is created. 
            // instead it should add a new node to the end of the tree if its null
        }

        if (valueToBeInserted < this.root.value)
        {
            this.root = this.root.left;
            this.AddNode(valueToBeInserted);
        }

        if (valueToBeInserted > this.root.value)
        {
            this.root = this.root.right;
            this.AddNode(valueToBeInserted);
        }
    }

    public void printTree()
    {
        // print recursively the values here.
    }
}

class TreeTest
{
    public void Test()
    {
        var tree = new Tree(new Node(100));
        tree.AddNode(20);
        tree.AddNode(100);
    }
}

Thanks.

What is the point of writing public int value { get; set; } instead of public int value;? — Paul Draper
– Paul Draper, Commented Nov 15, 2013 at 7:22
@PaulDraper: ya, no special case. thanks for bringing that up. But, do you know how I should write the function for AddNode ? — now he who must not be named.
– now he who must not be named., Commented Nov 15, 2013 at 7:25

Bernhard Barker · Accepted Answer · 2017-04-30 08:44:30Z

4

These lines replace the root:

this.root = this.root.left;
this.root = this.root.right;

You should instead pass a parameter to your recursive function.

You can also remove the this quantifiers - they're only necessary when you have a local variable with the same name or perhaps in some other corner cases.

Adding a helper function is useful / necessary since the root must be catered for separately.

Updated code:

public void AddNode(int valueToBeInserted)
{
    if (root == null)
    {
        root = new Node(valueToBeInserted);
    }
    else
    {
        AddNode(valueToBeInserted, root);
    }
}

private void AddNode(int valueToBeInserted, Node current)
{
    if (valueToBeInserted < current.value)
    {
        if (current.left == null)
            current.left = new Node(valueToBeInserted);
        else
            AddNode(valueToBeInserted, current.left);
    }

    if (valueToBeInserted > current.value)
    {
        if (current.right == null)
            current.right = new Node(valueToBeInserted);
        else
            AddNode(valueToBeInserted, current.right);
    }
}

edited Apr 30, 2017 at 8:44

answered Nov 15, 2013 at 7:25

Bernhard Barker

55.7k14 gold badges111 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rajesh Mishra Over a year ago

@nowhewhomustnotbenamed. How you tested it? clearly, there is no function "AddRoot" here, it should be "AddNode". Isn't it?

Bernhard Barker Over a year ago

@RajeshMishra Fixed.

Noctis · Accepted Answer · 2013-11-15 08:39:35Z

1

This statement will only be true the first time you run your code.

if (this.root == null)
{
    this.root = new Node(valueToBeInserted);
}

Nowhere does the this.root get set to null again... Normally you would code the add like this:

public void AddNode(int valueToBeInserted)
{
    if (this.root == null)
    {
        this.root = new Node(valueToBeInserted); 
    }

    if (valueToBeInserted < this.root.value)
    {
        this.root.left = this.AddNode(valueToBeInserted);
        this.root = this.root.left;
    }

    if (valueToBeInserted > this.root.value)
    {
        this.root.right = this.AddNode(valueToBeInserted);
        this.root = this.root.right;
    }
}

edited Nov 15, 2013 at 8:39

Noctis

11.8k3 gold badges46 silver badges86 bronze badges

answered Nov 15, 2013 at 7:25

Eugène

6865 silver badges10 bronze badges

Collectives™ on Stack Overflow

Recursive function implementation for Binary search tree

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related