Método iterativo para encontrar ancestros de un árbol binario dado

Dado un árbol binario, imprima todos los ancestros de una clave particular existente en el árbol sin usar la recursividad.
Aquí discutiremos la implementación del problema anterior. 

Ejemplos: 

Input : 
            1
        /       \
       2         7
     /   \     /   \
    3     5    8    9 
   /       \       /
  4         6     10 
Key = 6 

Output : 5 2 1
Ancestors of 6 are 5, 2 and 1.

La idea es utilizar un recorrido iterativo posterior al orden del árbol binario dado.  

Implementación:

// C++ program to print all ancestors of a given key
#include <bits/stdc++.h>
using namespace std;
 
// Structure for a tree node
struct Node {
    int data;
    struct Node* left, *right;
};
 
// A utility function to create a new tree node
struct Node* newNode(int data)
{
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// Iterative Function to print all ancestors of a
// given key
void printAncestors(struct Node* root, int key)
{
    if (root == NULL)
        return;
 
    // Create a stack to hold ancestors
    stack<struct Node*> st;
 
    // Traverse the complete tree in postorder way till
    // we find the key
    while (1) {
 
        // Traverse the left side. While traversing, push
        // the nodes into  the stack so that their right
        // subtrees can be traversed later
        while (root && root->data != key) {
            st.push(root); // push current node
            root = root->left; // move to next node
        }
 
        // If the node whose ancestors are to be printed
        // is found, then break the while loop.
        if (root && root->data == key)
            break;
 
        // Check if right sub-tree exists for the node at top
        // If not then pop that node because we don't need
        // this node any more.
        if (st.top()->right == NULL) {
            root = st.top();
            st.pop();
 
            // If the popped node is right child of top,
            // then remove the top as well. Left child of
            // the top must have processed before.
            while (!st.empty() && st.top()->right == root) {
                root = st.top();
                st.pop();
            }
        }
 
        // if stack is not empty then simply set the root
        // as right child of top and start traversing right
        // sub-tree.
        root = st.empty() ? NULL : st.top()->right;
    }
 
    // If stack is not empty, print contents of stack
    // Here assumption is that the key is there in tree
    while (!st.empty()) {
        cout << st.top()->data << " ";
        st.pop();
    }
}
 
// Driver program to test above functions
int main()
{
    // Let us construct a binary tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(7);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(8);
    root->right->right = newNode(9);
    root->left->left->left = newNode(4);
    root->left->right->right = newNode(6);
    root->right->right->left = newNode(10);
 
    int key = 6;
    printAncestors(root, key);
 
    return 0;
}

// Java program to print all
// ancestors of a given key
import java.util.*;
 
class GfG
{
 
// Structure for a tree node
static class Node
{
    int data;
    Node left, right;
}
 
// A utility function to
// create a new tree node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
    return node;
}
 
// Iterative Function to print
// all ancestors of a given key
static void printAncestors(Node root, int key)
{
    if (root == null)
        return;
 
    // Create a stack to hold ancestors
    Stack<Node> st = new Stack<Node> ();
 
    // Traverse the complete tree in
    // postorder way till we find the key
    while (1 == 1)
    {
 
        // Traverse the left side. While
        // traversing, push the nodes into
        // the stack so that their right
        // subtrees can be traversed later
        while (root != null && root.data != key)
        {
            st.push(root); // push current node
            root = root.left; // move to next node
        }
 
        // If the node whose ancestors
        // are to be printed is found,
        // then break the while loop.
        if (root != null && root.data == key)
            break;
 
        // Check if right sub-tree exists
        // for the node at top If not then
        // pop that node because we don't 
        // need this node any more.
        if (st.peek().right == null)
        {
            root = st.peek();
            st.pop();
 
            // If the popped node is right child of top,
            // then remove the top as well. Left child of
            // the top must have processed before.
            while (!st.isEmpty() && st.peek().right == root)
            {
                root = st.peek();
                st.pop();
            }
        }
 
        // if stack is not empty then simply
        // set the root as right child of
        // top and start traversing right
        // sub-tree.
        root = st.isEmpty() ? null : st.peek().right;
    }
 
    // If stack is not empty, print contents of stack
    // Here assumption is that the key is there in tree
    while (!st.isEmpty())
    {
        System.out.print(st.peek().data + " ");
        st.pop();
    }
}
 
// Driver code
public static void main(String[] args)
{
    // Let us construct a binary tree
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(7);
    root.left.left = newNode(3);
    root.left.right = newNode(5);
    root.right.left = newNode(8);
    root.right.right = newNode(9);
    root.left.left.left = newNode(4);
    root.left.right.right = newNode(6);
    root.right.right.left = newNode(10);
 
    int key = 6;
    printAncestors(root, key);
}
}
 
// This code is contributed
// by prerna saini

# Python program to print all ancestors of a given key
 
# A class to create a new tree node
class newNode:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None
 
# Iterative Function to print all ancestors of a
# given key
def printAncestors(root, key):
    if (root == None):
        return
 
    # Create a stack to hold ancestors
    st = []
 
    # Traverse the complete tree in postorder way till
    # we find the key
    while (1):
 
        # Traverse the left side. While traversing, push
        # the nodes into the stack so that their right
        # subtrees can be traversed later
        while (root and root.data != key):
            st.append(root) # push current node
            root = root.left # move to next node
 
        # If the node whose ancestors are to be printed
        # is found, then break the while loop.
        if (root and root.data == key):
            break
 
        # Check if right sub-tree exists for the node at top
        # If not then pop that node because we don't need
        # this node any more.
        if (st[-1].right == None):
            root = st[-1]
            st.pop()
 
            # If the popped node is right child of top,
            # then remove the top as well. Left child of
            # the top must have processed before.
            while (len(st) != 0 and st[-1].right == root):
                root = st[-1]
                st.pop()
 
        # if stack is not empty then simply set the root
        # as right child of top and start traversing right
        # sub-tree.
        root = None if len(st) == 0 else st[-1].right
 
    # If stack is not empty, print contents of stack
    # Here assumption is that the key is there in tree
    while (len(st) != 0):
        print(st[-1].data,end = " ")
        st.pop()
 
# Driver code
if __name__ == '__main__':
 
    # Let us construct a binary tree
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(7)
    root.left.left = newNode(3)
    root.left.right = newNode(5)
    root.right.left = newNode(8)
    root.right.right = newNode(9)
    root.left.left.left = newNode(4)
    root.left.right.right = newNode(6)
    root.right.right.left = newNode(10)
 
    key = 6
    printAncestors(root, key)
     
# This code is contributed by PranchalK.

// C# program to print all
// ancestors of a given key
using System;
using System.Collections.Generic;
 
class GfG
{
 
// Structure for a tree node
public class Node
{
    public int data;
    public Node left, right;
}
 
// A utility function to
// create a new tree node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
    return node;
}
 
// Iterative Function to print
// all ancestors of a given key
static void printAncestors(Node root, int key)
{
    if (root == null)
        return;
 
    // Create a stack to hold ancestors
    Stack<Node> st = new Stack<Node> ();
 
    // Traverse the complete tree in
    // postorder way till we find the key
    while (1 == 1)
    {
 
        // Traverse the left side. While
        // traversing, push the nodes into
        // the stack so that their right
        // subtrees can be traversed later
        while (root != null && root.data != key)
        {
            st.Push(root); // push current node
            root = root.left; // move to next node
        }
 
        // If the node whose ancestors
        // are to be printed is found,
        // then break the while loop.
        if (root != null && root.data == key)
            break;
 
        // Check if right sub-tree exists
        // for the node at top If not then
        // pop that node because we don't
        // need this node any more.
        if (st.Peek().right == null)
        {
            root = st.Peek();
            st.Pop();
 
            // If the popped node is right child of top,
            // then remove the top as well. Left child of
            // the top must have processed before.
            while (st.Count != 0 && st.Peek().right == root)
            {
                root = st.Peek();
                st.Pop();
            }
        }
 
        // if stack is not empty then simply
        // set the root as right child of
        // top and start traversing right
        // sub-tree.
        root = st.Count == 0 ? null : st.Peek().right;
    }
 
    // If stack is not empty, print contents of stack
    // Here assumption is that the key is there in tree
    while (st.Count != 0)
    {
        Console.Write(st.Peek().data + " ");
        st.Pop();
    }
}
 
// Driver code
public static void Main(String[] args)
{
    // Let us construct a binary tree
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(7);
    root.left.left = newNode(3);
    root.left.right = newNode(5);
    root.right.left = newNode(8);
    root.right.right = newNode(9);
    root.left.left.left = newNode(4);
    root.left.right.right = newNode(6);
    root.right.right.left = newNode(10);
 
    int key = 6;
    printAncestors(root, key);
}
}
 
// This code has been contributed by 29AjayKumar

<script>
 
// Javascript program to print all
// ancestors of a given key
class Node
{
    constructor(data)
    {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}
 
// A utility function to
// create a new tree node
function newNode(data)
{
    let node = new Node(data);
    return node;
}
 
// Iterative Function to print
// all ancestors of a given key
function printAncestors(root, key)
{
    if (root == null)
        return;
 
    // Create a stack to hold ancestors
    let st = [];
 
    // Traverse the complete tree in
    // postorder way till we find the key
    while (1 == 1)
    {
         
        // Traverse the left side. While
        // traversing, push the nodes into
        // the stack so that their right
        // subtrees can be traversed later
        while (root != null && root.data != key)
        {
             
            // Push current node
            st.push(root);
             
            // Move to next node
            root = root.left;
        }
 
        // If the node whose ancestors
        // are to be printed is found,
        // then break the while loop.
        if (root != null && root.data == key)
            break;
 
        // Check if right sub-tree exists
        // for the node at top If not then
        // pop that node because we don't
        // need this node any more.
        if (st[st.length - 1].right == null)
        {
            root = st[st.length - 1];
            st.pop();
 
            // If the popped node is right child of top,
            // then remove the top as well. Left child of
            // the top must have processed before.
            while (st.length != 0 &&
                st[st.length - 1].right == root)
            {
                root = st[st.length - 1];
                st.pop();
            }
        }
 
        // If stack is not empty then simply
        // set the root as right child of
        // top and start traversing right
        // sub-tree.
        root = st.length == 0 ? null :
            st[st.length - 1].right;
    }
 
    // If stack is not empty, print contents
    // of stack. Here assumption is that the
    // key is there in tree
    while (st.length != 0)
    {
        document.write(st[st.length - 1].data + " ");
        st.pop();
    }
}
 
// Driver code
 
// Let us construct a binary tree
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(7);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.left = newNode(8);
root.right.right = newNode(9);
root.left.left.left = newNode(4);
root.left.right.right = newNode(6);
root.right.right.left = newNode(10);
 
let key = 6;
printAncestors(root, key);
 
// This code is contributed by divyeshrabadiya07
 
</script>

5 2 1 

Análisis de Complejidad:

• Complejidad de tiempo: O(n)
• Complejidad espacial: O(n)

Este artículo es una contribución de Gautam Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.