c++ - How to fix below code for binary tree level order printing

Question

I have implemented below code for level order printing of nodes in a binary tree. However, it fails when a node has both left and right child.

For example, below is my binary tree.

 1
  \
   2
    \
     5
    /  \
   3    6
    \
     4  

Expected output is: 1 2 5 3 6 4 However, my code prints: 1 2 5 3 4 4

What is the mistake I am doing? feels like some pointer goof up.

Below are the functions I have written:

void printNodes(Node *arr[], int numOfNodes)
    {
        Node *outputArr[]={NULL};

        int j=0;

        for(int i=0; i<numOfNodes; i++)
        {
            printf("%d ",arr[i]->data);

            if(arr[i]->left!=NULL)
            {
                outputArr[j++]=arr[i]->left;
            }

            if(arr[i]->right!=NULL)
            {
                outputArr[j++]=arr[i]->right;
            }
        }

        if(j>0)
            printNodes(outputArr, j);
        else 
            return;
    }

    void levelOrder(Node * root) {
        Node *list[]={NULL};
        int ctr=0;

        if(root == NULL)
            return;

        printf("%d ",root->data);

        if(root->left != NULL)
            list[ctr++]=root->left;
        if(root->right != NULL)
            list[ctr++]=root->right;

        printNodes(list, ctr);
    }

I will paste below some driver code:

main() {

    Example myTree;
    Node* root = NULL;

    int t;
    int data;

    std::cin >> t;

    while(t-- > 0) {
        std::cin >> data;
        root = myTree.insert(root, data);
    }

    myTree.levelOrder(root);
    return 0;
}

标签： c++

Answer 1

Assuming you are doing what you are doing for some reason, educational or otherwise, just modifying that minimally to do what I think you want your approach to do, try this:

void printNodes(std::vector<Node*> list) {
    std::vector<Node*> newList;

    for(int i=0; i<list.size(); i++) {
        printf("%d ",list[i]->data);

        if(list[i]->left) newList.push_back(list[i]->left);
        if(list[i]->right) newList.push_back(list[i]->right);
    }

    if(!newList.empty()) printNodes(newList);
    else return;
}

void levelOrder(Node * root) {
    if(!root) return;
    std::vector<Node*> list;

    printf("%d ",root->data);

    if(root->left) list.push_back(root.left);
    if(root->right) list.push_back(root.right);;

    printNodes(list);
}

A better solution would probably be to not use recursion at all and do the usual Breadth 1st Traversal IMO.