Given a Binary Tree and an integer target. Find all the ancestors of the given target.
Note:
- The ancestor of node x is node y, which is at the upper level of node x, and x is directly connected with node y. Consider multiple levels of ancestors to solve this problem.
- In case there are no ancestors available, return an empty list.
Examples:
Input: 1 / \ 2 3 / \ / \ 4 5 6 8 / 7 target = 7 Output: [4 2 1]
Explanation: The given target is 7, if we go above the level of node 7, then we find 4, 2 and 1. Hence the ancestors of node 7 are 4 2 and 1
Input: 1 / \ 2 3 target = 1 Output: [ ]
Explanation: Since 1 is the root node, there would be no ancestors. Hence we return an empty list.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ no. of nodes ≤ 103
1 ≤ data of node ≤ 104
Approach 01:
-
C++
-
Python
class Solution {
public:
vector<int> Ancestors(Node* root, int target) {
vector<int> ancestors_list;
findAncestors(root, target, ancestors_list);
return ancestors_list;
}
private:
bool findAncestors(Node* node, int target, vector<int>& ancestors_list) {
if (!node) {
return false;
}
if (node->data == target) {
findAncestors(node->left, target, ancestors_list);
findAncestors(node->right, target, ancestors_list);
return true;
}
if (findAncestors(node->left, target, ancestors_list)) {
ancestors_list.push_back(node->data);
return true;
}
if (findAncestors(node->right, target, ancestors_list)) {
ancestors_list.push_back(node->data);
return true;
}
return false;
}
};
class Solution:
def Ancestors(self, root, target):
ancestors_list = []
def find_ancestors(node):
if not node:
return False
if node.data == target:
find_ancestors(node.left)
find_ancestors(node.right)
return True
if find_ancestors(node.left):
ancestors_list.append(node.data)
return True
if find_ancestors(node.right):
ancestors_list.append(node.data)
return True
return False
find_ancestors(root)
return ancestors_list