Predecesor de orden posterior de un Node en el árbol de búsqueda binaria

Dado un árbol binario y un Node en el árbol binario, encuentre el predecesor Postorder del Node dado. 

Ejemplos: 

Consider the following binary tree
              20            
           /      \         
          10       26       
         /  \     /   \     
       4     18  24    27   
            /  \
           14   19
          /  \
         13  15
Input :  4
Output : 10
Postorder traversal of given tree is 4, 13, 15, 
14, 19, 18, 10, 24, 27, 26, 20.

Input :  24
Output : 10

Una solución simple es almacenar primero el recorrido posterior al orden del árbol dado en una array, luego buscar linealmente el Node dado e imprimir el Node al lado. 
Complejidad de tiempo: O(n) 
Espacio auxiliar: O(n)
Una solución eficiente se basa en las siguientes observaciones. 

1. Si existe el hijo derecho de un Node dado, entonces el hijo derecho es el predecesor posterior al orden.
2. Si el hijo derecho no existe y el Node dado es hijo izquierdo de su padre, entonces su hermano es su predecesor Postorder.
3. Si no se cumple ninguna de las condiciones anteriores (el hijo izquierdo no existe y el Node dado no es el hijo derecho de su padre), entonces avanzamos usando punteros de padres hasta que ocurra uno de los siguientes. 
   • Llegamos a la raíz. En este caso, el predecesor Postorder no existe.
   • El Node actual (uno de los ancestros del Node dado) es el hijo derecho de su padre, en este caso, el predecesor posterior al orden es el hermano del Node actual.

// C++ program to find postorder predecessor of
// a node in Binary Tree.
#include <iostream>
using namespace std;
 
struct Node {
    struct Node *left, *right, *parent;
    int key;
};
 
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->left = temp->right = temp->parent = NULL;
    temp->key = key;
    return temp;
}
 
Node* postorderPredecessor(Node* root, Node* n)
{
    // If right child exists, then it is postorder
    // predecessor.
    if (n->right)
        return n->right;
 
    // If right child does not exist, then
    // travel up (using parent pointers)
    // until we reach a node which is right
    // child of its parent.
    Node *curr = n, *parent = curr->parent;
    while (parent != NULL && parent->left == curr) {
        curr = curr->parent;
        parent = parent->parent;
    }
 
    // If we reached root, then the given
    // node has no postorder predecessor
    if (parent == NULL)
        return NULL;
 
    return parent->left;
}
 
int main()
{
    Node* root = newNode(20);
    root->parent = NULL;
    root->left = newNode(10);
    root->left->parent = root;
    root->left->left = newNode(4);
    root->left->left->parent = root->left;
    root->left->right = newNode(18);
    root->left->right->parent = root->left;
    root->right = newNode(26);
    root->right->parent = root;
    root->right->left = newNode(24);
    root->right->left->parent = root->right;
    root->right->right = newNode(27);
    root->right->right->parent = root->right;
    root->left->right->left = newNode(14);
    root->left->right->left->parent = root->left->right;
    root->left->right->left->left = newNode(13);
    root->left->right->left->left->parent = root->left->right->left;
    root->left->right->left->right = newNode(15);
    root->left->right->left->right->parent = root->left->right->left;
    root->left->right->right = newNode(19);
    root->left->right->right->parent = root->left->right;
 
    Node* nodeToCheck = root->left->right;
 
    Node* res = postorderPredecessor(root, nodeToCheck);
 
    if (res) {
        printf("Postorder predecessor of %d is %d\n",
               nodeToCheck->key, res->key);
    }
    else {
        printf("Postorder predecessor of %d is NULL\n",
               nodeToCheck->key);
    }
 
    return 0;
}

// Java program to find postorder predecessor
// of a node in Binary Tree.
import java.util.*;
 
class GFG{
 
static class Node
{
    Node left, right, parent;
    int key;
};
 
static Node newNode(int key)
{
    Node temp = new Node();
    temp.left = temp.right = temp.parent = null;
    temp.key = key;
    return temp;
}
 
static Node postorderPredecessor(Node root, Node n)
{
     
    // If right child exists, then it is
    // postorder predecessor.
    if (n.right != null)
        return n.right;
 
    // If right child does not exist, then
    // travel up (using parent pointers)
    // until we reach a node which is right
    // child of its parent.
    Node curr = n, parent = curr.parent;
    while (parent != null && parent.left == curr)
    {
        curr = curr.parent;
        parent = parent.parent;
    }
 
    // If we reached root, then the given
    // node has no postorder predecessor
    if (parent == null)
        return null;
 
    return parent.left;
}
 
// Driver code
public static void main(String[] args)
{
    Node root = newNode(20);
    root.parent = null;
    root.left = newNode(10);
    root.left.parent = root;
    root.left.left = newNode(4);
    root.left.left.parent = root.left;
    root.left.right = newNode(18);
    root.left.right.parent = root.left;
    root.right = newNode(26);
    root.right.parent = root;
    root.right.left = newNode(24);
    root.right.left.parent = root.right;
    root.right.right = newNode(27);
    root.right.right.parent = root.right;
    root.left.right.left = newNode(14);
    root.left.right.left.parent = root.left.right;
    root.left.right.left.left = newNode(13);
    root.left.right.left.left.parent = root.left.right.left;
    root.left.right.left.right = newNode(15);
    root.left.right.left.right.parent = root.left.right.left;
    root.left.right.right = newNode(19);
    root.left.right.right.parent = root.left.right;
 
    Node nodeToCheck = root.left.right;
 
    Node res = postorderPredecessor(root, nodeToCheck);
 
    if (res != null)
    {
        System.out.printf("Postorder predecessor " +
                          "of %d is %d\n",
                          nodeToCheck.key, res.key);
    }
    else
    {
        System.out.printf("Postorder predecessor " +
                          "of %d is null\n",
                          nodeToCheck.key);
    }
}
}
 
// This code is contributed by Rajput-Ji

"""Python3 program to find postorder
predecessor of given node."""
 
# A Binary Tree Node
# Utility function to create a
# new tree node
class newNode:
 
    # Constructor to create a newNode
    def __init__(self, data):
        self.key = data
        self.left = None
        self.right = self.parent = None
 
def postorderPredecessor(root, n):
 
    # If right child exists, then it
    # is postorder predecessor.
    if (n.right) :
        return n.right
 
    # If right child does not exist, then
    # travel up (using parent pointers)
    # until we reach a node which is right
    # child of its parent.
    curr = n
    parent = curr.parent
    while (parent != None and
           parent.left == curr):
        curr = curr.parent
        parent = parent.parent
 
    # If we reached root, then the given
    # node has no postorder predecessor
    if (parent == None) :
        return None
 
    return parent.left
 
# Driver Code
if __name__ == '__main__':
 
    root = newNode(20)
    root.parent = None
    root.left = newNode(10)
    root.left.parent = root
    root.left.left = newNode(4)
    root.left.left.parent = root.left
    root.left.right = newNode(18)
    root.left.right.parent = root.left
    root.right = newNode(26)
    root.right.parent = root
    root.right.left = newNode(24)
    root.right.left.parent = root.right
    root.right.right = newNode(27)
    root.right.right.parent = root.right
    root.left.right.left = newNode(14)
    root.left.right.left.parent = root.left.right
    root.left.right.left.left = newNode(13)
    root.left.right.left.left.parent = root.left.right.left
    root.left.right.left.right = newNode(15)
    root.left.right.left.right.parent = root.left.right.left
    root.left.right.right = newNode(19)
    root.left.right.right.parent = root.left.right
 
    nodeToCheck = root.left.right
 
    res = postorderPredecessor(root, nodeToCheck)
 
    if (res) :
        print("Postorder predecessor of",
               nodeToCheck.key, "is", res.key)
     
    else:
        print("Postorder predecessor of",
               nodeToCheck.key, "is None")
 
# This code is contributed
# by SHUBHAMSINGH10

// C# program to find postorder
// predecessor of a node
// in Binary Tree.
using System;
class GFG{
 
class Node
{
  public Node left, right, parent;
  public int key;
};
 
static Node newNode(int key)
{
  Node temp = new Node();
  temp.left = temp.right =
              temp.parent = null;
  temp.key = key;
  return temp;
}
 
static Node postorderPredecessor(Node root,
                                 Node n)
{   
  // If right child exists,
  // then it is postorder
  // predecessor.
  if (n.right != null)
    return n.right;
 
  // If right child does not exist, then
  // travel up (using parent pointers)
  // until we reach a node which is right
  // child of its parent.
  Node curr = n, parent = curr.parent;
  while (parent != null &&
         parent.left == curr)
  {
    curr = curr.parent;
    parent = parent.parent;
  }
 
  // If we reached root, then the given
  // node has no postorder predecessor
  if (parent == null)
    return null;
 
  return parent.left;
}
 
// Driver code
public static void Main(String[] args)
{
  Node root = newNode(20);
  root.parent = null;
  root.left = newNode(10);
  root.left.parent = root;
  root.left.left = newNode(4);
  root.left.left.parent = root.left;
  root.left.right = newNode(18);
  root.left.right.parent = root.left;
  root.right = newNode(26);
  root.right.parent = root;
  root.right.left = newNode(24);
  root.right.left.parent = root.right;
  root.right.right = newNode(27);
  root.right.right.parent = root.right;
  root.left.right.left = newNode(14);
  root.left.right.left.parent = root.left.right;
  root.left.right.left.left = newNode(13);
  root.left.right.left.left.parent = root.left.right.left;
  root.left.right.left.right = newNode(15);
  root.left.right.left.right.parent = root.left.right.left;
  root.left.right.right = newNode(19);
  root.left.right.right.parent = root.left.right;
  Node nodeToCheck = root.left.right;
 
  Node res = postorderPredecessor(root, nodeToCheck);
 
  if (res != null)
  {
    Console.Write("Postorder predecessor " +
                  "of {0} is {1}\n",
                  nodeToCheck.key, res.key);
  }
  else
  {
    Console.Write("Postorder predecessor " +
                  "of {0} is null\n",
                  nodeToCheck.key);
  }
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program to find postorder
// predecessor of a node
// in Binary Tree.
 
class Node
{
    constructor()
    {
        this.left = null;
        this.right = null;
        this.parent = null;
        this.key = 0;
    }
};
 
function newNode(key)
{
  var temp = new Node();
  temp.left = temp.right =
              temp.parent = null;
  temp.key = key;
  return temp;
}
 
function postorderPredecessor(root, n)
{   
  // If right child exists,
  // then it is postorder
  // predecessor.
  if (n.right != null)
    return n.right;
 
  // If right child does not exist, then
  // travel up (using parent pointers)
  // until we reach a node which is right
  // child of its parent.
  var curr = n, parent = curr.parent;
  while (parent != null &&
         parent.left == curr)
  {
    curr = curr.parent;
    parent = parent.parent;
  }
 
  // If we reached root, then the given
  // node has no postorder predecessor
  if (parent == null)
    return null;
 
  return parent.left;
}
 
// Driver code
var root = newNode(20);
root.parent = null;
root.left = newNode(10);
root.left.parent = root;
root.left.left = newNode(4);
root.left.left.parent = root.left;
root.left.right = newNode(18);
root.left.right.parent = root.left;
root.right = newNode(26);
root.right.parent = root;
root.right.left = newNode(24);
root.right.left.parent = root.right;
root.right.right = newNode(27);
root.right.right.parent = root.right;
root.left.right.left = newNode(14);
root.left.right.left.parent = root.left.right;
root.left.right.left.left = newNode(13);
root.left.right.left.left.parent = root.left.right.left;
root.left.right.left.right = newNode(15);
root.left.right.left.right.parent = root.left.right.left;
root.left.right.right = newNode(19);
root.left.right.right.parent = root.left.right;
var nodeToCheck = root.left.right;
var res = postorderPredecessor(root, nodeToCheck);
if (res != null)
{
  document.write(`Postorder predecessor ` +
                `of ${nodeToCheck.key} is ${res.key}<br>`);
}
else
{
  document.write(`Postorder predecessor ` +
                `of ${nodeToCheck.key} is null<br>`);
}
 
// This code is contributed by famously.
</script>

Postorder predecessor of 18 is 19

Complejidad de tiempo: O(h) donde h es la altura del árbol binario dado 
Espacio auxiliar: O(1)