To find set of all nodes that are visible from left side of binary tree.

   vector<int> getLeftView(TreeNode<int> *root)
    {
         static vector<int> res;
       // Your code here
       if(root){
           res.push_back(root->data);
           if(root->left)
                getLeftView(root->left);
           else
                getLeftView(root->right);
       }
       return res;
}

For a single test case at a time it works fine. But when multiple test cases are run, the previous values in the vector is appended by the new values. How do I clear the vector before running the next test case?

CodePudding user response：

You used static because you need a single instance of the vector to be used across the recursion. But static is not the way; it causes there to be just one instance of the vector in the entire program as such.

There are various solutions, one of which is to split the function into the API and recursive part:

void getLeftViewRec(TreeNode<int> *root, vector<int> &res)
{
    if(root){
        res.push_back(root->data);
        if(root->left)
             getLeftView(root->left, res);
        else
             getLeftView(root->right, res);
    }
    return res;
}


vector<int> getLeftView(TreeNode<int> *root)
{
    vector<int> res;
    getLeftViewRec(root, res);
    return res;
}

Now what happens is that every time getLeftView is called, a new vector res is instantiated as a local variable. It then calls the recursive function getLeftViewRec which receives res by reference, and passes it to itself through the recursive calls, so the recursion is working with a single vector, accumulating into it.

CodePudding user response：

Using queue and a null pointer to mark the first element of each level. we insert a null pointer in the first and as reach that null pointer we mark bool as true and take the next element as our left view element,

// C   Code for the above iterative approach
#include <bits/stdc  .h>
using namespace std;

// Tree Node Structure contains data, left and right
// pointer
struct Node {
    int data;
    struct Node *left, *right;
};

// A utility function to
// create a new Binary Tree Node
struct Node* newNode(int item)
{
    struct Node* temp
        = (struct Node*)malloc(sizeof(struct Node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

// function to get the left view of binary tree in vector
vector<int> leftView(Node* root)
{

    // store the left view
    vector<int> ans;

    // Base Case : Empty Tree
    if (!root)
        return ans;
    

    // Create an empty queue and enque root node and null
    queue<Node*> q;
    q.push(root);
    q.push(NULL);
    bool ok = true;

    // Traverse till queue is not empty
    while (!q.empty()) {
        // get the front node and dequeue it from queue
        auto it = q.front();
        q.pop();

        // if the front node is null do following steps
        if (it == NULL) {
            if (ok == false)
                ok = true;
            

            if (q.size() == 0)
                break;
            
            else
                q.push(NULL);
            
        }
        // else do the following steps
        else {
            if (ok) {
                ans.push_back(it->data);
                ok = false;
            }

            if (it->left)
                q.push(it->left);
            
            if (it->right)
                q.push(it->right);
            
        }
    }

    // return the left view
    return ans;
}

// driver code to test above code on a test case
int main()
{
    /*
    Input :
                10
                / \
                2    3
            / \ / \
            7 8 12 15
                        /
                        14

    Output : 10 2 7 14
*/
    // let's build above shown tree
    Node* root = newNode(10);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(8);
    root->right->right = newNode(15);
    root->right->left = newNode(12);
    root->right->right->left = newNode(14);

    // call leftview function and store output in vec
    vector<int> vec = leftView(root);
    // traverse on left view and print each element
    for (int x : vec)
        cout << x << " ";
    cout << endl;

    return 0;
}