Encuentra el padre de un Node en el árbol binario dado

Dado un árbol y un Node, la tarea es encontrar el padre del Node dado en el árbol. Imprime -1 si el Node dado es el Node raíz.
Ejemplos: 

Input: Node = 3
     1
   /   \
  2     3
 / \
4   5
Output: 1

Input: Node = 1
     1
   /   \
  2     3
 /       \
4         5
         /
        6
Output: -1

Enfoque: escriba una función recursiva que tome el Node actual y su padre como argumentos (el Node raíz se pasa con -1 como padre). Si el Node actual es igual al Node requerido, imprima su padre y regrese; de ​​lo contrario, llame a la función recursivamente para sus hijos y el Node actual como padre.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
/* A binary tree node has data, pointer
to left child and a pointer
to right child */
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
// Recursive function to find the
// parent of the given node
void findParent(struct Node* node,
                int val, int parent)
{
    if (node == NULL)
        return;
 
    // If current node is the required node
    if (node->data == val) {
 
        // Print its parent
        cout << parent;
    }
    else {
 
        // Recursive calls for the children
        // of the current node
        // Current node is now the new parent
        findParent(node->left, val, node->data);
        findParent(node->right, val, node->data);
    }
}
 
// Driver code
int main()
{
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    int node = 3;
 
    findParent(root, node, -1);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
/* A binary tree node has data, pointer
to left child and a pointer
to right child */
static class Node
{
    int data;
    Node left, right;
    Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
// Recursive function to find the
// parent of the given node
static void findParent(Node node,
                       int val, int parent)
{
    if (node == null)
        return;
 
    // If current node is the required node
    if (node.data == val)
    {
 
        // Print its parent
        System.out.print(parent);
    }
    else
    {
 
        // Recursive calls for the children
        // of the current node
        // Current node is now the new parent
        findParent(node.left, val, node.data);
        findParent(node.right, val, node.data);
    }
}
 
// Driver code
public static void main(String []args)
{
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    int node = 3;
 
    findParent(root, node, -1);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of
# the above approach
 
''' A binary tree node has data, pointer
to left child and a pointer
to right child '''
class Node:
   
    def __init__(self, data):
       
        self.data = data
        self.left = None
        self.right = None
 
# Recursive function to find the
# parent of the given node
def findParent(node : Node,
               val : int,
               parent : int) -> None:
    if (node is None):
        return
 
    # If current node is
    # the required node
    if (node.data == val):
       
        # Print its parent
        print(parent)
    else:
       
        # Recursive calls
        # for the children
        # of the current node
        # Current node is now
        # the new parent
        findParent(node.left,
                   val, node.data)
        findParent(node.right,
                   val, node.data)
 
# Driver code
if __name__ == "__main__":
 
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    node = 3
    findParent(root, node, -1)
 
# This code is contributed by sanjeev2552

// C# implementation of the approach
using System;
     
class GFG
{
 
/* A binary tree node has data, pointer
to left child and a pointer
to right child */
public class Node
{
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
// Recursive function to find the
// parent of the given node
static void findParent(Node node,
                         int val, int parent)
{
    if (node == null)
        return;
 
    // If current node is the required node
    if (node.data == val)
    {
 
        // Print its parent
        Console.Write(parent);
    }
    else
    {
 
        // Recursive calls for the children
        // of the current node
        // Current node is now the new parent
        findParent(node.left, val, node.data);
        findParent(node.right, val, node.data);
    }
}
 
// Driver code
public static void Main(String []args)
{
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    int node = 3;
 
    findParent(root, node, -1);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the approach
     
/* A binary tree node has data, pointer
to left child and a pointer
to right child */
class Node
{
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Recursive function to find the
// parent of the given node
function findParent(node, val, parent)
{
    if (node == null)
        return;
 
    // If current node is the required node
    if (node.data == val)
    {
 
        // Print its parent
        document.write(parent);
    }
    else
    {
 
        // Recursive calls for the children
        // of the current node
        // Current node is now the new parent
        findParent(node.left, val, node.data);
        findParent(node.right, val, node.data);
    }
}
 
// Driver code
var root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
var node = 3;
 
findParent(root, node, -1);
 
 
</script>

1

Complejidad temporal : O(N).
Espacio Auxiliar : O(N).