Gokhale Education Society’s
R. H. Sapat College of Engineering,
Management Studies & Research, Nashik-422007
Department of Computer Engineering
PBL of Fundamentals of Data Structure
On
Ancestors of Binary Tree Node Without Recursion
AY 2024-25 SEM-III
By
Roll No. 1-7
Prof. Mrunal Joshi Dr. D.V. Patil
Subject Teacher HOD
INDEX
[Link]. Contents
1. Problem Statement
2. Objectives
3. Theory
4. Code
5. Output
6. Conclusion
Problem Statement :
Write a python program to find ancestors of given binary tree node without
recursion.
Objectives :
1. Tree Construction : Convert a list of integers into a binary tree where the
integers represent node values. The list should be processed level-wise,
starting from the root and then filling each level from left to right.
2. Ancestor Retrieval : Find and print all ancestor nodes of a specified target
node. Ancestors are defined as all nodes on the path from the target node up to
the root of the tree.
3. Non-Recursive Approach : Implement the solution using iterative methods
instead of recursion to avoid issues related to deep recursion or stack overflow
in large trees.
4. User Interaction : Allow users to input the tree structure and target node, then
display the ancestors of the target node clearly.
5. Code Readability : Write clean,well-documented that is easy to understand
and maintain ,with comments explaining logic behind key operations.
Theory :
Binary Tree :
Binary tree is a data structure where each node has at most two children ,
referred to as the left child and the right child.
The top node is known as the root, and nodes without children are called leaves.
Ancestors :
Ancestor of anode are all nodes on the path from that node to root.
Level Order Transversal :
Level-order traversal involves visiting nodes level by level from the root.
This traversal is useful for constructing a tree from a list of values.
For example, consider the following Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
Following are different input keys and their ancestors in the above tree :
Input Key List of Ancestors
1
2 1
3 1
4 2 1
5 2 1
6 3 1
7 3 1
8 4 2 1
9 5 2 1
10 7 3 1
For above binary tree level-order transversal would visit node in this order :
[1,2,3,4,5,6,7,8,9,10]
Stack :
A Stack is a linear data structure that holds a linear , ordered sequence of
elements. It is an abstract data type.
A Stack works on the LIFO process (Last In First Out) , i.e., the element that was
inserted last will be removed first.
Algorithm :
[Link] the Tree : Initialize the root of the tree with the first element of the list.
[Link] a queue to keep track of nodes that need to have their children assigned.
[Link] each node, assign its left and right children based on subsequent elements
in the list.
4. Continue this process until all elements have been processed.
5. Find and Print Ancestors : Use a stack to traverse the tree and a dictionary to
keep track of each node's parent.
6. Traverse the tree and fill the dictionary with parent-child relationships.
Once the target node is found, trace back using the dictionary to collect and print
the ancestors.
Code :
class Node:
def init (self, key):
"""Initialize given key node with given key and no child"""
[Link] = None
[Link] = None
[Link] = key
def insertLevelOrder(arr):
"""Inserts nodes in a binary tree level-wise from the given array."""
if not arr:
return None
root = Node(arr[0])
queue = [root]
i=1
n = len(arr)
while i < n:
current = [Link](0)
if i < n and arr[i] != -1:
[Link] = Node(arr[i])
[Link]([Link])
i += 1
if i < n and arr[i] != -1:
[Link] = Node(arr[i])
[Link]([Link])
i += 1
return root
def printAncestors(root, target):
"""Prints ancestors of the target node."""
if root is None:
print("Tree is empty.")
return False
stack = [root]
parent_map = {}
while stack:
node = [Link]()
if [Link]:
[Link]([Link])
parent_map[[Link]] = node
if [Link]:
[Link]([Link])
parent_map[[Link]] = node
if [Link] == target:
ancestors = []
while node in parent_map:
node = parent_map[node]
[Link]([Link])
print("Ancestors:", " ".join(map(str, ancestors)))
return True
print("Target node not found in the tree.")
return False
def takeInput():
"""Takes input to build the binary tree and specify the target node."""
arr = list(map(int, input("Enter the binary tree nodes in level order (use -1 for
null nodes): ").split()))
root = insertLevelOrder(arr)
target = int(input("Enter the target node: "))
return root, target
# Main Function
if name == " main ":
root, target = takeInput()
print("Ancestors of node", target, "are: ")
printAncestors(root, target)
Output :
Conclusion :
This program successfully builds a binary tree from a list of integers and finds the
ancestors of a specified node. By using an iterative approach, the code avoids
recursion, making it suitable for environments with limited stack space.
The use of a queue for tree construction and a stack for finding ancestors ensures
that the tree is processed level by level and ancestors are traced efficiently.
This approach is effective for understanding basic tree operations and managing
hierarchical data.
Submitted By :
Sr. Roll Name of Students Signature
No No.
01 1 Kothawade Aniket Devendra
02 2 Kshirsagar Yash Millind
03 3 Kumbhar Yogeshwar Vitthal
04 6 Mahajan Umesh Arun
05 7 Mahajan Yashodip Murlidhar
