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

Question

I am trying to implement a Binary Tree, NOT Binary Search Tree, in C#. I implemented the below code which is working fine but is not what I am looking for. Basically I am trying to implement a Complete Binary Tree, but with my below code, I am getting an unbalanced binary tree.

Input : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Desired Output : 

                        10
                     /       \
                 20            30
               /    \         /  \
            40        50    60    70
           /  \      /
         80    90  100     


Current Output : 
                                10
                              /    \
                            20      30
                                  /    \
                                40      50    
                                       /   \
                                     60     70
                                           /  \
                                         80    90  
                                              /
                                            100   

Here is my code :

  class Node 
  {
    public int data;
    public Node left;
    public Node right;

    public Node() 
    {
      data = 0;
      left = null;
      right = null;
    }
  }

  class Tree 
  {
    private Node root;

    public Tree() 
    {
      root = null;
    }

    public void AddNode(int data)
    {
      root = AddNode(root, data);
    }

    public Node AddNode(Node node, int data) 
    {
      if (node == null)
      {
        node = new Node();
        node.data = data;
      }
      else
      {
        if (node.left == null)
        {
          node.left = AddNode(node.left, data);
        }
        else
        {
          node.right = AddNode(node.right, data);
        }
      }
      return node;
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      int[] nodeData = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
      Tree tree1 = new Tree();
      foreach (int i in nodeData)
      {
        tree1.AddNode(i);
      }
      Console.ReadKey();
    }
  }

I know the issue is in my AddNode(Node node, int data) {...} function's else block, but I am not able to figure out the resolution.

I tried to look for solution online but most of the places its Binary Search Tree implementation. One of the solution i liked is here but the solution is passing the input array as arguments for recursive calling, which I don't know will be efficient or not in case of a very large tree. There were several other posts but none of them is resolving my problem.

Although I am implementing it in C#, but more specifically I am looking the logic to fix my AddNode(...) function so I am fine with the algorithm if not the code implementation.

Any help?

Answer 1

Trees are by definition recursive data structures.

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; }
}

As such, constructing them using recursion is far more intuitive.

Input: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100

Desired output --complete binary tree:

               10
           /        \
         20          30
      /     \     /      \
    40       50  60      70
  /   \     /    
80     90  100

Matching index of input:

               0
           /       \
          1         2
      /     \     /     \
    3        4   5       6
  /   \     /    
 7     8   9

A pattern emerges, for a node with index i:

• the left child has index 2*i + 1
• the right child has index 2*i + 2

With the base case for recursion,

i >= input.length

all we need to do is call the recursive method on the root.

class TreeBuilder<T>
{
    public Node<T> Root { get; }

    public TreeBuilder(params T[] data)
    {
        Root = buildTree(data, 0);
    }

    private Node<T> buildTree(T[] data, int i)
    {
        if (i >= data.Length) return null;
        Node<T> next = new Node<T>(data[i]);
        next.Left = buildTree(data, 2 * i + 1);
        next.Right = buildTree(data, 2 * i + 2);
        return next;
    }
}

Usage:

int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data);
Node<int> tree = builder.Root;

---

Switching API, a couple of ways to add nodes one by one:

• traversing the tree from the root down (absolute)
• travelling from the previously added node (relative)
• maintaining an ordered collection of nodes that don't have two child nodes

As the second one involves longer travel distances (2 * height of the tree) and the third one has already been implemented (queue for bookkeeping), let's have a look at the first.

This time, visualizing the node count at a given position:

               1
           /        \
         2           3
      /     \     /     \
    4        5   6       7 
  /   \     /    
8      9   10 

Mapping to binary representation:

               1
           /        \
         10          11
      /     \     /     \
   100     101  110     111 
  /   \     /    
1000  1001 1010 

If we ignore the leftmost bit, again, a pattern emerges. We can use the bits as a road map, or in this case node map.

class TreeBuilder<T>
{
    private int level;
    private int nodeCount;
    public Node<T> Root { get; }

    public TreeBuilder(T data)
    {
        Root = new Node<T>(data);
        nodeCount = 1;
        level = 0;
    }

    public void addNode(T data)
    {
        nodeCount++;
        Node<T> current = Root;
        if (nodeCount >= Math.Pow(2, level + 1)) level++;
        for (int n=level - 1; n>0; n--)
            current = checkBit(nodeCount, n) ? current.Left : current.Right;
        if (checkBit(nodeCount, 0))
            current.Left = new Node<T>(data);
        else
            current.Right = new Node<T>(data);
    }

    private bool checkBit(int num, int position)
    {
        return ((num >> position) & 1) == 0;
    }
}

Usage:

int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data[0]);
for (int i=1; i<data.Length; i++)
{
    builder.addNode(data[i]);
}
Node<int> tree = builder.Root;

Answer 2

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)