K-th ancestor of a node in Binary Tree

/* C# program to calculate Kth ancestor of given node */
using System;
using System.Collections.Generic;

class GfG 
{
    
// A Binary Tree Node 
public class Node 
{ 
    public int data; 
    public Node left, right; 
}

// function to generate array of ancestors 
static void generateArray(Node root, int []ancestors) 
{ 
    // There will be no ancestor of root node 
    ancestors[root.data] = -1; 

    // level order traversal to 
    // generate 1st ancestor 
    LinkedList<Node> q = new LinkedList<Node> (); 
    q.AddLast(root); 

    while(q.Count != 0) 
    { 
        Node temp = q.First.Value; 
        q.RemoveFirst(); 

        if (temp.left != null) 
        { 
            ancestors[temp.left.data] = temp.data; 
            q.AddLast(temp.left); 
        } 

        if (temp.right != null) 
        { 
            ancestors[temp.right.data] = temp.data; 
            q.AddLast(temp.right); 
        } 
    } 
} 

// function to calculate Kth ancestor 
static int kthAncestor(Node root, int n, int k, int node) 
{ 
    // create array to store 1st ancestors 
    int []ancestors = new int[n + 1]; 

    // generate first ancestor array 
    generateArray(root,ancestors); 

    // variable to track record of number of 
    // ancestors visited 
    int count = 0; 

    while (node != -1) 
    { 
        node = ancestors[node]; 
        count++; 

        if(count == k) 
            break; 
    } 

    // print Kth ancestor 
    return node; 
} 

// Utility function to create a new tree node 
static Node newNode(int data) 
{ 
    Node temp = new Node(); 
    temp.data = data; 
    temp.left = null;
    temp.right = null; 
    return temp; 
} 

// Driver program to test above functions 
public static void Main(String[] args) 
{ 
    // Let us create binary tree shown in above diagram 
    Node root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 

    int k = 2; 
    int node = 5; 

    // print kth ancestor of given node 
    Console.WriteLine(kthAncestor(root,5,k,node)); 
}
} 

// This code has been contributed by 29AjayKumar

// C# program for finding
// kth ancestor of a particular node
using System;

// Structure for a node
public class Node {
    public int data;
    public Node left, right;

    public Node(int x)
    {
        this.data = x;
        this.left = this.right = null;
    }
}

class GFG {

    static int k = 1;

    // Program to find kth ancestor
    static bool ancestor(Node root, int item)
    {
        if (root == null)
            return false;

        // Element whose ancestor is
        // to be searched
        if (root.data == item) {

            // Reduce count by 1
            k = k - 1;
            return true;
        }
        else {

            // Checking in left side
            bool flag = ancestor(root.left, item);
            if (flag) {
                if (k == 0) {

                    // If count = 0 i.e. element is found
                    Console.Write("[" + root.data + "] ");
                    return false;
                }

                // If count !=0 i.e. this is not the
                // ancestor we are searching for
                // so decrement count
                k = k - 1;
                return true;
            }

            // Similarly Checking in right side
            bool flag2 = ancestor(root.right, item);
            if (flag2) {
                if (k == 0) {
                    Console.Write("[" + root.data + "] ");
                    return false;
                }
                k = k - 1;
                return true;
            }
        }
        return false;
    }

    // Driver code
    static public void Main()
    {
        Node root = new Node(1);
        root.left = new Node(4);
        root.left.right = new Node(7);
        root.left.left = new Node(3);
        root.left.right.left = new Node(8);
        root.right = new Node(2);
        root.right.right = new Node(6);

        int item = 3;
        int loc = k;
        bool flag = ancestor(root, item);

        if (flag)
            Console.WriteLine("Ancestor doesn't exist");
        else
            Console.WriteLine("is the " + (loc)
                              + "th ancestor of [" + (item)
                              + "]");
    }
}

// This code is contributed by patel2127

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class MainClass {
    public static int KthAncestor(TreeNode root,
                                  TreeNode node, int k)
    {
        // Initialize a stack to keep track of the path from
        // the root to the target node
        Stack<TreeNode> s = new Stack<TreeNode>();
        List<int> ancestors = new List<int>();
        bool found = false;

        // Traverse the binary tree from the root node
        while (root != null || s.Count > 0) {
            // If the current node is not null, push it onto
            // the stack and move to its left child
            if (root != null) {
                s.Push(root);
                root = root.left;
            }
            else {
                // If the current node is null, pop the top
                // element from the stack
                TreeNode temp = s.Pop();

                // If the top element is the target node,
                // break out of the loop
                if (temp.val == node.val) {
                    found = true;
                    break;
                }

                // Otherwise, move to its right child
                if (temp.right != null) {
                    root = temp.right;
                }
            }
        }

        // If the target node is not found, return -1
        if (!found) {
            return -1;
        }

        // Pop elements from the stack and add their values
        // to the ancestors vector until we reach the kth
        // ancestor or the stack becomes empty
        while (s.Count > 0 && k > 0) {
            TreeNode temp = s.Pop();
            ancestors.Add(temp.val);
            k--;
        }

        // If the stack becomes empty before we reach the
        // kth ancestor, return -1
        if (k > 0) {
            return -1;
        }

        // Return the value of the kth ancestor
        return ancestors[ancestors.Count - 1];
    }

    public static void Main()
    {
        /* Example tree:
               1
             /   \
            2     3
           / \
          4   5 */
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        int k = 2;
        int kthAncestorVal
            = KthAncestor(root, root.left.left, k);

        Console.WriteLine(
            "The " + k + "th ancestor of node "
            + root.left.left.val + " is " + kthAncestorVal);
    }
}