Where is the flaw in my algorithm for adding a node to a binary tree?

Question

My method(s) look(s) like

static Node _root = null;

static void AddToTree(int val)
{
    AddToTree(val, ref _root);
}

static void AddToTree(int val, ref Node root)
{
    if(root == null)
        root = new Node() { Val = val };
    Node left = root.Left, right = root.Right;
    if(root.Val > val)
        AddToTree(val, ref left);
    else if(root.Val < val)
        AddToTree(val, ref right);
}

and how I see that it's failing is I run

    int[] vals = { 2, 1, 5, 3, 8 };
    foreach(int i in vals)
        AddToTree(i);
    Print();

which uses

static void Print()
{
    if(_root == null)
        return;
    LinkedList<int> vals = new LinkedList<int>();
    Queue<Node> q = new Queue<Node>();
    q.Enqueue(_root);
    while(q.Count > 0)
    {
        Node front = q.Dequeue();
        vals.AddLast(front.Val);
        if(front.Right != null)
            q.Enqueue(front.Right);
        if(front.Left != null)
            q.Enqueue(front.Left);
    }
    Console.WriteLine(string.Join(",", vals));
}

and the output I see is

2

i.e. the first element added and no other elements.

Any idea where I'm going wrong?

Did you try debugging your code by placing breakpoints and stepping through it? — CodeCaster, Feb 03 '17 at 08:50

score 7 · Accepted Answer · edited May 23 '17 at 10:29

7

This code sequence does not do what you think it does:

Node left = root.Left;
Foo(ref left);

You're passing left by reference, not root.Left. Now when Foo() reassigns left, only left will be affected, not root.Left.

Of course you can't pass properties by reference, so the solution would be to reassign root.Left = left after Foo() returns.

edited May 23 '17 at 10:29

Community

1
1

answered Feb 03 '17 at 08:52

CodeCaster

147,647
23
218
272

Where is the flaw in my algorithm for adding a node to a binary tree?

1 Answers1