Find all the ancestors of a given node in a binary tree | FACE Prep

Find all the ancestors of a given node in a binary tree | FACE Prep

Find Ancestors of a Node in Binary Tree | FACE Prep

Introduction

Finding the ancestors of a given node in a binary tree is a common problem in data structures and algorithms. This problem has applications in tree traversal, genealogy-based computations, and hierarchical data processing. In this article, we will explore two approaches to solving this problem: iterative and recursive methods.

Understanding the Problem Statement

Given a binary tree and a node, we need to find and print all the ancestors of that node. For example, consider the following binary tree:

                    15
                  /    \  
                12      18  
               /       /   \
              8       13    24  
                             /   \
                            22    27

Expected Output

NodeAncestors
15
1215
1815
812, 15
1312, 15
2418, 15
2224, 18, 15
2724, 18, 15

Approaches to Solve the Problem

There are two primary ways to find the ancestors of a given node:

1. Iterative Approach

Algorithm:

  1. Input the binary tree and the key_node whose ancestors need to be found.
  2. Perform iterative post-order traversal.
  3. Store the ancestors in a stack while traversing.
  4. Stop the traversal once the key_node is found.
  5. Print the stack containing the ancestors.

Code Implementation (Iterative Approach):

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.data = key

def find_ancestors(root, key):
    if not root:
        return []
    stack = []
    parent = {}
    stack.append(root)
    parent[root] = None
    
    while stack:
        node = stack.pop()
        if node.data == key:
            break
        if node.right:
            stack.append(node.right)
            parent[node.right] = node
        if node.left:
            stack.append(node.left)
            parent[node.left] = node
    
    ancestors = []
    while parent.get(node):
        ancestors.append(parent[node].data)
        node = parent[node]
    
    return ancestors

# Example Usage:
root = Node(15)
root.left = Node(12)
root.right = Node(18)
root.left.left = Node(8)
root.left.right = Node(13)
root.right.right = Node(24)
root.right.right.left = Node(22)
root.right.right.right = Node(27)

print(find_ancestors(root, 22))  # Output: [24, 18, 15]

2. Recursive Approach

Algorithm:

  1. Input the binary tree and the key_node.
  2. Perform recursive post-order traversal.
  3. Traverse the left and right subtrees recursively.
  4. If the key_node is found, return the ancestor path.

Code Implementation (Recursive Approach):

def find_ancestors_recursive(root, key, ancestors=[]):
    if not root:
        return False
    if root.data == key:
        return True
    
    if find_ancestors_recursive(root.left, key, ancestors) or find_ancestors_recursive(root.right, key, ancestors):
        ancestors.append(root.data)
        return True
    return False

# Example Usage:
ancestors = []
find_ancestors_recursive(root, 22, ancestors)
print(ancestors)  # Output: [24, 18, 15]

Key Differences Between Iterative and Recursive Approaches

FeatureIterative ApproachRecursive Approach
Space ComplexityO(N) (Stack usage)O(N) (Recursive stack)
Time ComplexityO(N)O(N)
Ease of ImplementationModerateEasy

Conclusion

Finding ancestors of a given node in a binary tree is a crucial problem in hierarchical data management. Both iterative and recursive methods provide efficient solutions. The choice between the two depends on preference and constraints such as memory and stack usage.

Find all the ancestors of a given node in a binary tree

 

 

c