Ancestors in Binary Tree | Problem of the Day | GeeksForGeeks

[@mathematics3398]

Timestamp
0:0:00 Problem Statement
0:0:51 Solution
0:5:19 Pseudo Code
0:10:35 Code - Python
0:12:14 Code - C++

[@mathematics3398]

class Solution {
public:
bool found = false;
int ans_index = -1;
void get_ancestor(struct Node *root, int target, int index, vector& ans) {
if (!root or found)
return;
if (root->data == target) {
found = true;
ans_index = index;
return;
}
if (index >= ans.size())
ans.push_back(root->data);
else
ans[index] = root->data;
get_ancestor(root->left, target, index + 1, ans);
get_ancestor(root->right, target, index + 1, ans);
}
vector Ancestors(struct Node *root, int target) {
vector ans;
if (!root or root->data == target)
return ans;
found = false;
ans_index = -1;
vector temp;
get_ancestor(root, target, 0, temp);
if (!found)
return ans;
for (int i = ans_index - 1; i >= 0; i--)
ans.push_back(temp[i]);
return ans;
}
};

[@mathematics3398]

class Solution:
def get_ancestor(self, root, target, index, ans):
if not root or self.found:
return
if root.data == target:
self.found = True
self.ans_index = index
return
if index >= len(ans):
ans.append(root.data)
else:
ans[index] = root.data
self.get_ancestor(root.left, target, index + 1, ans)
self.get_ancestor(root.right, target, index + 1, ans)
def Ancestors(self, root, target):
'''
:param root: root of the given tree.
:return: None, print the space separated post ancestors of given target., don't print new line
'''
if not root:
return []
if root.data == target:
return []
temp = []
ans = []
self.found = False
self.ans_index = -1
self.get_ancestor(root, target, 0, temp)
if self.found == False:
return []
ans = list(reversed(temp[:self.ans_index]))
return ans