Skip to main content

Path to Given Node

Problem​

Given a Binary Tree A containing N nodes.

You need to find the path from Root to a given node B.

NOTE:

  • No two nodes in the tree have same data values.
  • You can assume that B is present in the tree A and a path always exists.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
vector<int> ans;
int check = 0;
void traversal(TreeNode* root, int B) {
    if (!root) return;
    if (root->val == B) {
        check = 1;
        ans.push_back(root->val);
        return;
    }
    traversal(root->left, B);
    if (check == 1) {
        ans.push_back(root->val);
        return;
    }
    traversal(root->right, B);
    if (check == 1) ans.push_back(root->val);
}

vector<int> Solution::solve(TreeNode* A, int B) {
    ans.clear();
    check = 0;
    traversal(A, B);
    reverse(ans.begin(), ans.end());
    return ans;
}