Simple solution using level order traversal


#1
#define PA pair<TreeNode*, TreeNode*>

vector<int> Solution::solve(TreeNode* root, int key) {
    vector<int> solution;
    if(root == NULL)
        return solution;
        
    queue<PA> q;
    q.push(make_pair(root, nullptr));
    q.push(make_pair(nullptr, nullptr));
    vector<PA> levelNodes;
    bool levelFound = false;
    TreeNode* keyParent = nullptr;
    
    while(!q.empty()){
        PA temp = q.front();
        q.pop();
        if(temp.first == nullptr){
            if(!q.empty())
                q.push(make_pair(nullptr, nullptr));
                
            if(levelFound) break;
            
            levelNodes.clear();
        }
        else{
            
            if(temp.first->val == key){
                keyParent = temp.second;
                levelFound = true;
            }
            else
                levelNodes.push_back(make_pair(temp.first, temp.second));
                
            if(temp.first->left != NULL)
                q.push(make_pair(temp.first->left, temp.first));
            if(temp.first->right != NULL)
                q.push(make_pair(temp.first->right, temp.first));
        }
    }
    for(auto node: levelNodes){
        if(node.second == keyParent)
            continue;
        solution.push_back(node.first->val);
    }

    return solution;
}