To store the binary tree in an array with null values in the missing position

Question

I want to store the binary tree in the array with null values at the missing nodes.

For eg:

Input:

Output:{1,2,3,4,5,0,6}

I have tried linear traversal of the binary tree in the array, but I want null in the missing nodes positions of the tree.

std::vector< int > levelorder( tree *root){
    queue<tree*> q; 
    tree* temp;
    q.push(root);
    while(!q.empty()){
        temp=q.front();
        q.pop();
        arr.push_back(temp->data);
        if(temp->left && temp->right)
        {
            q.push(temp->left);
            q.push(temp->right);
        }
        else if(temp->left && !temp->right)
        {
            q.push(temp->left);
            arr.insert(0);
        }
        else if(temp->right && !temp->left)
        {
            q.push(temp->right);
            arr.push_back(0);
        }

    }
    return arr;
}

int main() 
{ 

    tree *root = newNode(1);  
    root->left = newNode(2);  
    root->right = newNode(3);  
    root->left->left = newNode(4);  
    root->left->right = newNode(5);
    root->right->right = newNode(6);

    cout<<"Level Order traversal of binary tree is :"<<endl; 
    levelorder(root);
    for(int i =0; i<arr.size(); i++)
    {
        cout<< arr[i]<<" ";
    } 

    return 0; 
}

I am getting output:{1,2,3,0,4,5,6} But I want the output as: {1,2,3,4,5,0,6}

I think you'll have to push nulls into q, and when you get a null from q add a zero to the array then. The non-null numbers on the level get added to arr when the q entry is processed, not when they are queued. — Rup
– Rup, Commented May 7, 2019 at 14:08
In your example, only a leaf is missing. What do you expect if a whole branch is missing? — Gilles-Philippe Paillé
– Gilles-Philippe Paillé, Commented May 7, 2019 at 14:19
if in my example 6 is also missing then I want output as:{1,2,3,4,5} — Utkarsh Goyal
– Utkarsh Goyal, Commented May 7, 2019 at 14:23

Gilles-Philippe Paillé · Accepted Answer · 2019-06-14 13:48:30Z

3

Algorithm

The following code supports missing sub-trees and stop as soon as no meaningful nodes are present:

std::vector<int> levelorder(tree *root){
    int null_in_queue = 0;
    std::queue<tree*> q;
    std::vector<int> arr;
    q.push(root);
    while(q.size() != null_in_queue){
        tree* temp=q.front();
        q.pop();
        if(!temp)
        {
           arr.push_back(0);
           q.push(nullptr);
           q.push(nullptr);
           null_in_queue++; // One was removed, two were added
        }
        else
        {
            arr.push_back(temp->data);
            q.push(temp->left);
            q.push(temp->right);
            if (!temp->left) null_in_queue++;
            if (!temp->right) null_in_queue++;
        }
    }
    return arr;
}

It pushes virtual nodes (nullptr) in the queue and count the number of virtual nodes. When only virtual nodes are remaining, it terminates.

Complexity

The time and memory complexity of this algorithm is O(n), where n is the size of the output array. The size of this array is at most the node count (minus one) of a full tree up to the deepest node. For a tree of depth d, the algorithm has complexity O(2^d).

Details: The code in the loop is constant (amortized) and the q vector contains nodes and virtual nodes, which contains at most 2^(d+1) nodes (an additional row of virtual nodes will be added before the algorithm finishes). This means that the whole algorithm will execute in O(2^(d+1)) ~ O(2*2^d) ~ O(2^d).

edited Jun 14, 2019 at 13:48

answered May 7, 2019 at 14:34

Gilles-Philippe Paillé

3,2941 gold badge11 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Utkarsh Goyal Over a year ago

An error is coming while pushing the nullptr,Error is: 'nullptr' was not declared in this scope

Gilles-Philippe Paillé Over a year ago

Your compiler may not support the nullptr keyword (it appeared in C++11). Replace nullptr with 0.

Utkarsh Goyal Over a year ago

what will be the time complexity for this function

Gilles-Philippe Paillé Over a year ago

@UtkarshGoyal I added a paragraph describing the complexity of the algorithm.

Quimby · Accepted Answer · 2019-05-07 14:37:45Z

1

Assuming that the empty nodes are properly initialized to nullptr:

while(!q.empty()){
    tree* temp=q.front();
    q.pop();
    if(!temp)
       arr.push_back(0);
    else if (temp->left || temp->right)//Only recurse into internal nodes, not leafs
    {
        arr.push_back(temp->data);
        q.push(temp->left);
        q.push(temp->right);
    }
}

I would like to note that this won't print missing subtrees, only missing leafs. Please specify if it should.

edited May 7, 2019 at 14:37

answered May 7, 2019 at 14:13

Quimby

19.4k4 gold badges40 silver badges61 bronze badges

2 Comments

Utkarsh Goyal Over a year ago

the output is {1,2,3,4,5,0,6,0,0,0,0,0,0} why these extra zeros are coming in the end

Quimby Over a year ago

Because those nodes in the lowest level are also missing leafs, both of them. This is not probably what you wanted, sorry ,will edit the code shortly.

Collectives™ on Stack Overflow

To store the binary tree in an array with null values in the missing position

2 Answers 2

Algorithm

Complexity

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Algorithm

Complexity

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related