Path to Given Node

Path to Given Node - InterviewBitInterviewBit

Using Recursive Preorder Traversal

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
vector<int> res;

void getPath(TreeNode *root, int target, vector<int> &path) {
    if(!root) return;
    
    path.push_back(root->val);
    if(root->val == target) {
        res = path;
        return;
    }
    getPath(root->left, target, path);
    getPath(root->right, target, path);
    path.pop_back();
}

vector<int> Solution::solve(TreeNode* A, int B) {
    res.clear();
    vector<int> path;
    getPath(A, B, path);
    return res;
}