How to construct a binary tree in level order

Question

I'm learning data structures and trying to construct a binary tree by inserting nodes in a level order, but having little trouble in doing that. I want to insert nodes to a binary tree just by knowing the no of nodes that are there in the tree currently by traversing directly to the parent node without backtracking. This is what I've written so far

Tree.cpp

#include <iostream>
#include <cstdlib>
#include <cmath>


struct treeStruct {
    int data;

    struct treeStruct* parent;
    struct treeStruct* left;
    struct treeStruct* right;

    treeStruct() {
        data = 0;

        parent = NULL;
        left = NULL;
        right = NULL;
    }
};

void printInOrder(treeStruct* root) {
    if(root != NULL) {
        std::cout << root->data << "\t";
        printInOrder(root->left);
        printInOrder(root->right);
    }
}


void printPreOrder(treeStruct* root) {
    if(root != NULL) {
        printPreOrder(root->left);
        std::cout << root->data << "\t";
        printPreOrder(root->right);
    }   
}


void printPostOrder(treeStruct* root) {
    if(root != NULL) {
        printPostOrder(root->left);
        printPostOrder(root->right);
        std::cout << root->data << "\t";
    }
}


treeStruct* insertNode(treeStruct* parent, int data, int dir) {
    treeStruct* node = new treeStruct();

    if(parent == NULL) {
        node->data = data;
    }
    else {
        if(dir == 1) {
            node->data = data;
            node->parent = parent;
            parent->left = node;
        }
        else if(dir == 2) {
            node->data = data;
            node->parent = parent;
            parent->right = node;
        }
    }   

    return node;
}


treeStruct* constructInLevelTree(int* data, int len) { //having trouble in here
    int level = -1;
    int noOfNodes = 0;
    treeStruct* root = NULL;

    for(int i = 0; i < len; ++i) {
        if(level == -1) {
            root = insertNode(NULL, data[i], 0);
            ++level;
            ++noOfNodes;
        }
        else if(pow(2, level) >= noOfNodes) {
            treeStruct* node = root;
            treeStruct* parent = root->parent;
            int scanCount = 0;

            while(scanCount < noOfNodes) {
                if((scanCount % 2) == 0) {
                    if(node != NULL) {
                        parent = node;
                        node = node->left;
                    }
                }
                else {
                    if(node != NULL) {
                        parent = node;
                        node = node->right;
                    }
                }

                ++scanCount;
            }

            if((scanCount % 2) == 0)
                insertNode(parent, data[i], 1);
            else
                insertNode(parent, data[i], 2);

            ++noOfNodes;
        }
        else {
            ++level;
        }
    }

    return root;
}


int main(int argc, char* argv[]) {
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    treeStruct* root = constructInLevelTree(data, sizeof(data) / sizeof(int));

    printInOrder(root);
    printPreOrder(root);
    printPostOrder(root);

    return EXIT_SUCCESS;
}

Answer 1

This is what I wrote after the suggestions given by @ Md Golam Rahman Tushar and @nkvns

Tree.cpp

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>


struct treeStruct {
    int data;

    struct treeStruct* parent;
    struct treeStruct* left;
    struct treeStruct* right;

    treeStruct() {
        data = 0;

        parent = NULL;
        left = NULL;
        right = NULL;
    }
};

void printInOrder(treeStruct* root) {
    if(root != NULL) {
        std::cout << root->data << "\t";
        printInOrder(root->left);
        printInOrder(root->right);
    }
}


void printPreOrder(treeStruct* root) {
    if(root != NULL) {
        printPreOrder(root->left);
        std::cout << root->data << "\t";
        printPreOrder(root->right);
    }   
}


void printPostOrder(treeStruct* root) {
    if(root != NULL) {
        printPostOrder(root->left);
        printPostOrder(root->right);
        std::cout << root->data << "\t";
    }
}


void insertNode(treeStruct** parent, int data, int dir) {
    treeStruct* node = new treeStruct();

    if(*parent != NULL) {
        if(dir == 1) {
            node->data = data;
            node->parent = *parent;
            (*parent)->left = node;
        }
        else if(dir == 0) {
            node->data = data;
            node->parent = *parent;
            (*parent)->right = node;
        }
    }
    else {
        node->data = data;
        *parent = node;
    }
}


void getStackTrace(int nodeNo, std::vector<char>& stackTrace) {
    stackTrace.clear();
    int res;

    do {
        nodeNo = nodeNo / 2;
        if((nodeNo == 1) || (nodeNo == 0))
            stackTrace.push_back('T');
        else if(nodeNo % 2 == 0)
            stackTrace.push_back('L');
        else
            stackTrace.push_back('R');
    } while(nodeNo > 1);
}


treeStruct* constructInLevelTree(int* data, int len) {
    int noOfNodes = 0;
    treeStruct* root = NULL;
    std::vector<char> stackTrace;

    for(int i = 0; i < len; ++i) {
        if(i == 0) {
            insertNode(&root, data[i], -1);
            std::cout << "\ninserted root node" << std::endl;
        }
        else {
            getStackTrace(noOfNodes + 1, stackTrace);
            treeStruct* parentNode;
            std::vector<char>::reverse_iterator stackItr = stackTrace.rbegin();

            std::cout << "\nfor data " << data[i] << " taverse is:" << std::endl;
            while(stackItr != stackTrace.rend()) {
                std::cout << (*stackItr) << "\t";
                if((*stackItr) == 'T')
                    parentNode = root;
                else if((*stackItr) == 'L')
                    parentNode = parentNode->left;
                else
                    parentNode = parentNode->right;

                ++stackItr;
            }

            insertNode(&parentNode, data[i], (i % 2));
        }

        ++noOfNodes;
    }

    return root;
}


int main(int argc, char* argv[]) {
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for(int i = 0; i < sizeof(data) / sizeof(int); ++i)
        std::cout << data[i] << "\t";

    std::cout << "\n" << std::endl;

    treeStruct* root = constructInLevelTree(data, sizeof(data) / sizeof(int));

    std::cout << "\nIn Order traversal" << std::endl;
    printInOrder(root);

    std::cout << "\nPre Order traversal" << std::endl;
    printPreOrder(root);

    std::cout << "\nPost Order traversal" << std::endl;
    printPostOrder(root);

    std::cout <<"\n" << std::endl;

    return EXIT_SUCCESS;
}

Answer 2

If you want to create tree in level order, at any step of creation your tree is going to be complete binary tree (Please note difference between complete and full binary tree). You can use this invariant effectively. There are two possible approaches here

1. Using arrays: Array can be used to represent complete binary tree effectively. int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; if in a level node are inserted left to right and index runs starts from 1 (root at index 1), For any node at index n, children are at index (2*n) and (2*n + 1) For any node at index n, parent is at index n/2 So if you want to create tree level wise, just keep adding new node at the end of the array. If you follow Algorithm book by Cormen, check heapsort for more details on this representation
2. Using linked structure: If you want to use a linked structure (a node struct having parent, left and right child pointers), you can still use the fact that in complete binary tree if nodes are marked by level traversal (left to right), parent of a node at index n will be at index n/2. So before inserting new node you can compute the path from root. For example when adding 11, traversal path should be root -> 2 -> 5 -> 11.