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.
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
Node | Ancestors |
---|---|
15 | – |
12 | 15 |
18 | 15 |
8 | 12, 15 |
13 | 12, 15 |
24 | 18, 15 |
22 | 24, 18, 15 |
27 | 24, 18, 15 |
There are two primary ways to find the ancestors of a given node:
key_node
whose ancestors need to be found.key_node
is found.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]
key_node
.key_node
is found, return the ancestor path.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]
Feature | Iterative Approach | Recursive Approach |
---|---|---|
Space Complexity | O(N) (Stack usage) | O(N) (Recursive stack) |
Time Complexity | O(N) | O(N) |
Ease of Implementation | Moderate | Easy |
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.