Given a binary tree of size  N, a node, and a positive integer k., Your task is to complete the function kthAncestor(), the function should return the kth ancestor of the given node in the binary tree. If there does not exist any such ancestor then return -1.
Note: It is guaranteed that the node exists in the tree.
Example 1:
Input:
     K = 2
     Node = 4
Output: 1
Explanation:
Since, K is 2 and node is 4, so we
first need to locate the node and
look k times its ancestors.
Here in this Case node 4 has 1 as his
2nd Ancestor aka the Root of the tree.
 
Example 2:
Input:
k=1 
node=3
      1
    /   \
    2     3
Output:
1
Explanation:
K=1 and node=3 ,Kth ancestor of node 3 is 1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1<=N<=10^{4}
1<= K <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



def kthAncestor(root,k, node):

    #code here

Solutions:
def solve(root, node):
	if root == None:
		return None
	if root.data == node:
		return root
	la = solve(root.left, node)
	ra = solve(root.right, node)
	if la and (not ra):
		m -= 1
		if m <= 0:
			m = 11111
			return root
		return la
	elif not la and ra:
		m -= 1
		if m <= 0:
			m = 11111
			return root
		return ra
	return None

def kthAncestor(root, k, node):
	m = k

	def solve(root, node):
		nonlocal m
		if root == None:
			return None
		if root.data == node:
			return root
		la = solve(root.left, node)
		ra = solve(root.right, node)
		if la and (not ra):
			m -= 1
			if m <= 0:
				m = 11111
				return root
			return la
		elif not la and ra:
			m -= 1
			if m <= 0:
				m = 11111
				return root
			return ra
		return None
	a = solve(root, node)
	if a == None or a.data == node:
		return -1
	return a.data


def kthAncestor(root, k, node):
	arr = []

	def sol(root, node):
		if root is None:
			return False
		arr.append(root)
		if root.data == node:
			return True
		if sol(root.left, node) or sol(root.right, node):
			return True
		arr.pop()
	sol(root, node)
	if k > len(arr) - 1:
		return -1
	else:
		return arr[len(arr) - k - 1].data


def kthAncestor(root, k, node):

	def LCA(root, path, tar):
		if root == None:
			return
		if root.data == tar:
			ans.append(path + [root.data])
		LCA(root.left, path + [root.data], tar)
		LCA(root.right, path + [root.data], tar)
	ans = []
	LCA(root, [], node)
	ans1 = ans[0]
	if k >= len(ans1):
		return -1
	return ans1[len(ans1) - k - 1]


def findNode(root, node):
	if root == None:
		return None
	if root.data == node:
		return root
	l = findNode(root.left, node)
	r = findNode(root.right, node)
	if l != None:
		return l
	if r != None:
		return r
	else:
		return None

def kthAncestor(root, k, node):
	parent = {}
	q = [root]
	while len(q) > 0:
		temp = q[0]
		q.pop(0)
		if temp.left != None:
			parent[temp.left] = temp
			q.append(temp.left)
		if temp.right != None:
			parent[temp.right] = temp
			q.append(temp.right)
	node = findNode(root, node)
	vis = {}
	q = node
	ans = -1
	while k >= 0:
		temp = q
		if k == 0:
			ans = temp.data
			break
		if parent.get(temp) != None:
			q = parent[temp]
		else:
			break
		k -= 1
	return ans


def add_nodes(root, node, ans):
	if not root:
		return False
	if root.data == node:
		return True
	if add_nodes(root.left, node, ans) or add_nodes(root.right, node, ans):
		ans.append(root.data)
		return True
	return False

def kthAncestor(root, k, node):
	ans = []
	add_nodes(root, node, ans)
	if len(ans) == 0 or len(ans) < k:
		return -1
	return ans[k - 1]


def generateArray(root, ancestors):
	ancestors[root.data] = -1
	q = []
	q.append(root)
	while len(q):
		temp = q[0]
		q.pop(0)
		if temp.left:
			ancestors[temp.left.data] = temp.data
			q.append(temp.left)
		if temp.right:
			ancestors[temp.right.data] = temp.data
			q.append(temp.right)

def kthAncestor(root, k, node):
	ancestors = [0] * 10001
	generateArray(root, ancestors)
	count = 0
	while node != -1:
		node = ancestors[node]
		count += 1
		if count == k:
			break
	return node