Kth Ancestor

Problem Statement

Kth Ancestor in a Tree | Practice | GeeksforGeeks

Pattern:

---

Solution

static class Ancestor {
	int distance = -10;
	Ancestor(int distance){
		this.distance = distance;
	}
}
 
Node findAncestor(Node root, Ancestor anc, int node) {
	if(root == null) return null;
	if(root.data == node) {
		anc.distance--;
		return root;
	}
	
	Node left = findAncestor(root.left, anc, node);
	Node right = findAncestor(root.right, anc, node);
	
	// get non-null ancestor value
	Node ans = (left!=null)? left : right;
	
	// node found, ancestor not already found
	if(ans != null && anc.distance > -1) {
		if (anc.distance == 0) ans = root;
		anc.distance--;
	}
	return ans;
}
 
public int kthAncestor (Node root, int k , int node){
	Ancestor anc = new Ancestor(k);
	Node res = findAncestor(root,anc, node);
	if(anc.distance == -1) return res.data;
	return -1;
}

Notes