Implementing a complete binary tree, not binary search tree in C#

You need to populate the tree level by level. A level n has 2^n nodes, that is there are 2^n paths from the root. Each path can be encoded as an n-bit number (0 means take a left branch, 1 means take a right). That is, to populate nth level,

    for path from 0 to 2^n - 1
        value = get_next_value()
        node = root
        for level = 0 to n - 1
            if path & 0x1 == 0
                node = node->left
            else
                node = node->right
            ++level
            path >>= 1
        if path == 0
            node->left = new node(value)
        else
            node->right = new node(value)

This algorithm can solve your problem in pretty simple and efficient way.

Consider this Node class:

public class Node<T>
{
     public Node(T data) 
     {
         Data = data;
     }

    public T Data { get; }

    public Node<T>  Left { get; set;}

    public Node<T>  Right { get; set;}
}

This class will help you to compose your tree:

public class TreeBuilder<T>
{
    private readonly Queue<Node<T>> _previousNodes;

    public Node<T> Root { get; }

    public TreeBuilder(T rootData)
    {
        Root = new Node<T>(rootData)
        _previousNodes = new Queue<Node<T>>();
        _previousNodes.Enqueue(Root);
    }

    public void AddNode(T data)
    {
        var newNode = new Node<T>(data);
        var nodeToAddChildTo = _previousNodes.Peek();
        if(nodeToAddChildTo.Left == null)
        {
           nodeToAddChildTo.Left = node; 
        }
        else
        {
            nodeToAddChildTo.Right = node;
            _previousNodes.Dequeue();
        }      
        _previousNodes.Enqueue(newNode);
    } 
}

The logic behind AddNode method is based on FIFO methodology so we will use Queue<T> in the implementation.

We will start with the first node and attach to it a left child first (and add it to the queue afterwards) and then we will attach to it a right one (and also add it to the queue afterwards) and only after we will attach both we will remove it from the queue and start to attach children to it's left child (which is the next in the queue) and when we will finish with it we will start to attach children to it's right child (which will be the next in the queue), we will do this operation constantly from left to right from the top to the bottom until the tree will be composed.

Now you can use it from your main method like this:

public class Program
{
    public static void Main(string[] args)
    {
        int[] values = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        var treeBuilder = new TreeBuilder<int>(values[0]);
        foreach (int value in values.Skip(1))
        {
            treeBuilder.AddNode(value);
        }
        //here you can use treeBuilder Root property as an entry point to the tree
    }
}

Here is another way to get your answer without tracking left, right and/or parent. In fact the Node class becomes real simple, the Tree class does the work when you call tree1.Root ... below I used the constructor to add the values, but I have included the AddNodes method, where you can add a new node as many values as you would like to add with a single call.

  class Node<T>
  {
    public T Data { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }

    public override string ToString()
    {
      return Data.ToString();
    }
  }


  class Tree<T>
  {
    private readonly List<T> list;

    private static readonly Func<List<T>, int, Node<T>> LeftFunc = (l, i) =>
    {
      var lix = Convert.ToInt32(Convert.ToString(i, 2) + "0", 2) - 1;
      return l.Count > lix ? new Node<T> {Data = l[lix], Left = LeftFunc(l, lix + 1), Right = RightFunc(l, lix + 1) } : null;
    };

    private static readonly Func<List<T>, int, Node<T>> RightFunc = (l, i) =>
    {
      var rix = Convert.ToInt32(Convert.ToString(i, 2) + "1", 2) - 1;
      return l.Count > rix ? new Node<T> { Data = l[rix], Left = LeftFunc(l, rix + 1), Right = RightFunc(l, rix + 1) } : null;
    };

    public Node<T> Root => list.Any() ? new Node<T>{Data=list.First(), Left = LeftFunc(list,1), Right= RightFunc(list,1)} : null;

    public Tree(params T[] data)
    {
      list = new List<T>(data);
    }

    public int Count => list.Count;

    public void AddNodes(params T[] data)
    {
      list.AddRange(data);
    }


    public double Levels => Math.Floor(Math.Log(list.Count,2))+1;

    public override string ToString()
    {
      return  (list?.Count ?? 0).ToString();
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
      var tree1 = new Tree<int>(nodeData);



      Console.ReadKey();
    }

For fun I created an extension that will write the tree to the console, to help visualize the tree. In order to use this you will need to ensure that the Node and Tree classes are public and add a Values property to the Tree class as well. So your Tree class would look like this:

  public class Tree<T>
  {
    private readonly List<T> list;

    private static readonly Func<List<T>, int, Node<T>> LeftFunc = (l, i) =>
    {
      var lix = Convert.ToInt32(Convert.ToString(i, 2) + "0", 2) - 1;
      return l.Count > lix ? new Node<T> {Data = l[lix], Left = LeftFunc(l, lix + 1), Right = RightFunc(l, lix + 1) } : null;
    };

    private static readonly Func<List<T>, int, Node<T>> RightFunc = (l, i) =>
    {
      var rix = Convert.ToInt32(Convert.ToString(i, 2) + "1", 2) - 1;
      return l.Count > rix ? new Node<T> { Data = l[rix], Left = LeftFunc(l, rix + 1), Right = RightFunc(l, rix + 1) } : null;
    };

    public Node<T> Root => list.Any() ? new Node<T>{Data=list.First(), Left = LeftFunc(list,1), Right= RightFunc(list,1)} : null;

    public Tree(params T[] data)
    {
      list = new List<T>(data);
    }

    public int Count => list.Count;

    public void AddNodes(params T[] data)
    {
      list.AddRange(data);
    }

    public IEnumerable<T> Values => list.ToArray();

    public double Levels => Math.Floor(Math.Log(list.Count,2))+1;

    public override string ToString()
    {
      return  (list?.Count ?? 0).ToString();
    }
  }

And here is the extensions class:

  public static class TreeAndNodeExtensions
  {
    public static void Write<T>(this Tree<T> tree)
    {
      var baseMaxNodes = Convert.ToInt32(Math.Pow(2, tree.Levels - 1));

      // determine the required node width based on the the last two levels and their value lengths...
      var nodeWidth = Math.Max(tree.Values.Skip(Convert.ToInt32(Math.Pow(2, tree.Levels - 2) - 1)).Max(n => n.ToString().Length), tree.Values.Skip(Convert.ToInt32(Math.Pow(2, tree.Levels - 1) - 1)).Max(n => n.ToString().Length) + 1) + 1;

      var baseWidth = baseMaxNodes * nodeWidth;
      Console.CursorLeft = baseWidth/2;
      tree.Root.Write(baseWidth);
    }

    private static void Write<T>(this Node<T> node, int nodeWidth, int level=0)
    {
      var cl = Console.CursorLeft;
      var ct = Console.CursorTop;

      if (Console.CursorLeft >= Convert.ToInt32(Math.Ceiling(node.Data.ToString().Length / 2.0)))
      {
        Console.CursorLeft -= Convert.ToInt32(Math.Ceiling(node.Data.ToString().Length / 2.0));
      }
      Console.Write(node.Data);
      if (node.Left != null)
      {
        var numCenter = cl - nodeWidth/4;
        Console.CursorLeft = numCenter;
        Console.CursorTop = ct + 2;
        Console.Write('/');
        Console.CursorTop = ct + 1;
        Console.Write(new string('_',cl-Console.CursorLeft));
        Console.CursorLeft = numCenter;
        Console.CursorTop = ct+3;
        node.Left.Write(nodeWidth/2, level+1);
      }

      if (node.Right != null)
      {
        var numCenter = cl + nodeWidth/4;
        Console.CursorLeft = cl;
        Console.CursorTop = ct + 1;
        Console.Write(new string('_', numCenter-cl-1));
        Console.CursorTop = ct + 2;
        Console.Write('\\');
        Console.CursorLeft = numCenter;
        Console.CursorTop = ct+3;
        node.Right.Write(nodeWidth/2,level + 1);
      }

      Console.SetCursorPosition(cl,ct);
    }
  }

Then you can update your program to use this extension:

  class Program
  {
    static void Main(string[] args)
    {
      var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80,90,100 };
      var tree1 = new Tree<int>(nodeData);

      tree1.Write();

      Console.ReadKey();
    }
  }

And you should see this:

                   10
           __________________
          /                  \
         20                  30
      ________            ________
     /        \          /        \
    40        50        60        70
    __        _
   /  \      /
  80  90   100

Each node will need to know it's parent, root node being the exception as it will have a null parent. Then each node will need to know which path it passed a value down last. Then when a node is asked to add a child it will go in sequence of: left, right, parent, left, right, parent, ... (root node being the exception as it will skip parent and will just alternate left, right, left, right ...)

I quickly adjusted your code to make it work as you intended, this could be much cleaner with a little time.

 class Node
  {
    private readonly Node parent;
    private Direction lastPath;

    public int Data { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }

    public Node(int data, Node parent = null)
    {
      Data = data;
      this.parent = parent;
    }

    public Node AddChild(int data)
    {
      if (Left == null)
      {
        lastPath = Direction.Left;
        Left = new Node(data, this);
        return this;
      }
      if (Right == null)
      {
        lastPath = Direction.Right;
        Right = new Node(data, this);
        return parent ?? this;
      }

      if (lastPath == Direction.Parent || parent==null && lastPath == Direction.Right)
      {
        lastPath = Direction.Left;
        return Left.AddChild(data);
      }

      if (lastPath == Direction.Left)
      {
        lastPath = Direction.Right;
        return Right.AddChild(data);
      }

      lastPath = Direction.Parent;
      return parent?.AddChild(data);
    }
  }

  enum Direction
  {
    Left,
    Right,
    Parent
  }

  class Tree
  {
    public Node Root { get; private set; }
    private Node current;

    public void AddNode(int data)
    {
      if (current == null)
      {
        Root = new Node(data);
        current = Root;
      }
      else
      {
        current = current.AddChild(data);
      }
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
      var tree1 = new Tree();

      foreach (var data in nodeData)
      {
        tree1.AddNode(data);
      }
      Console.ReadKey();
    }
  }

To answer your question:

Passing an array is done by passing the function a reference to the array. So in terms of performance, it is exactly the same as passing an object of any type (https://msdn.microsoft.com/en-us/library/bb985948.aspx).

Personnaly speaking, I'm not a big fan of recursive functions that always pass the same object, neither of constructors calling recursive functions which will call constructors.

Without arrays, here is a solution:

One interesting thing to notice is that in such trees, the node address can be used to find a node if you start addressing from 1:

                0001
        0010            0011
    0100    0101    0110   0111
1000

So if you keep track of the node count in your tree, you know that the next item to add will be at address 1001.

To do that properly, we can find the parent node (which is 1001 shifted right once : 100) then decide if we add left or right (depending on 1001 modulo 2 = 1 : must add to the right).

So here is the code that could do it:

Node class

//Having a generic here allows you to create a tree of any data type
class Node<T> 
{
    public T Data { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
    public Node(T Data)
    {
        this.Data = Data;
    }
}

Tree class

class Tree<T>
{
    Node<T> root = null;
    int nodeCount = 0;

    public void AddNode(T Data)
    {
        AddNode(new Node<T>(Data));
    }

    public void AddNode(Node<T> Node)
    {
        nodeCount++;
        if (root == null)
            root = Node;
        else
        {
            //First we find the parent node
            Node<T> parent = FindNodeWithAddress(nodeCount >> 1);
            //Then we add left or right
            if (nodeCount % 2 == 0)
                parent.Left = Node;
            else
                parent.Right = Node;
        }
    }

    private Node<T> FindNodeWithAddress(int address)
    {
        if (address == 1)
            return root;
        //To find the proper address we use the same trick
        //We first find our parent's address
        Node<T> parent = FindNodeWithAddress(address >> 1);
        //Then we go left or right
        return (address % 2 == 0 ? parent.Left : parent.Right);
    }
}

Have you tried implementing it using an array?

You would use an array, and an int in which to save the last position used for any position pos the left "child node" would be in position 2*pos the right "child node" would be in position 2*pos+1 and a "father node" would be in position pos/2

(don't consider this code to be syntactically correct, it is just an example)

template<class T>
class CompleteBinTree<T>{
    private int[] arr;
    private int arrSize;
    private int pos;

    public CompleteBinTree(){
        arrSize = 100;
        arr = new int[arrSize]//you can always change this number
        int pos = 1; //you can use 0 instead of 1, but this way it's easier to understand
    }

    public AddNode(T t){
        if(pos + 1 == arrSize){
            int[] aux = int[arrSize];
            for(int i = 0; i < arrSize; i++)
                aux[i] = arr[i];
            arr = aux[i];
            arrSize = arrSize * 2;
        }
            arr[pos] = t;
            pos++;
    }

    public IndexOfLeftSon(int x){
        return 2*x;
    }

    public IndexOfRightSon(int x){
        return 2*x + 1;
    }

    public DeleteNode(int x){
        for(int i = x; i < pos; i++)
            arr[i] = arr[i+1];
    }
}

Given that you really want to build a tree of allocated nodes, not an array as others have suggested, there is a very simple algorithm: Use a queue of locations (left or right child of given node or else the root) to expand the tree in top-down levels. Add new locations at the tail and remove from the head to add each successive node. No recursion.

Sorry I don't have access to a C# environment at the moment, so I'll have show this in Java. Translation should be pretty straightforward.

import java.util.ArrayDeque;
import java.util.Deque;

public class CompleteBinaryTree {
  final Deque<Location> queue = new ArrayDeque<>();

  /** Build a tree top-down in levels left-to-right with given node values. */
  Node build(int [] vals) {
    Node root = null;   
    queue.clear();
    queue.add(new Location(root, Location.Kind.ROOT));
    for (int val : vals) {
      Location next = queue.pollFirst();
      switch (next.kind) {
      case ROOT: root = addNode(val); break;
      case LEFT: next.node.left = addNode(val); break;
      case RIGHT: next.node.right = addNode(val); break;
      }
    }
    return root;
  } 

  /** Create a new node and queue up locations for its future children. */
  Node addNode(int val) {
    Node node = new Node(val);
    queue.addLast(new Location(node, Location.Kind.LEFT));
    queue.addLast(new Location(node, Location.Kind.RIGHT));
    return node;
  }

  static class Node {
    final int val;
    Node left, right;
    Node(int val) {
      this.val = val;
    }
    void print(int level) {
      System.out.format("%" + level + "s%d\n", "", val);
      if (left != null) left.print(level + 1);
      if (right != null) right.print(level + 1);
    }
  }

  static class Location {
    enum Kind { ROOT, LEFT, RIGHT }
    final Node node;
    final Kind kind;
    Location(Node node, Kind kind) {
      this.node = node;
      this.kind = kind;
    }
  }

  public static void main(String [] args) {
    int [] vals = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
    new CompleteBinaryTree().build(vals).print(1);
  }
}

When run, this produces, as you'd hope,

10
 20
  40
   80
   90
  50
   100
 30
  60
  70