Python program to query for ancestor-descendant relationship in a tree














































Python program to query for ancestor-descendant relationship in a tree



Description:
  1. Given a binary tree.
  2. We are given two nodes and we need to find the relationship between them.
  3. That is whether 1st node is an ancestor or not of the 2nd node.



l = [] #stores the ancestors of a given descendant node #class for creating a binary tree class Node: def __init__(self,data): self.data = data self.left = None self.right = None #function for checking the ancestors of given descendant def ancestors(root, target): if root == None: return False if root.data == target: return True if (ancestors(root.left, target) or ancestors(root.right,target)): l.append(root.data) return True return False #implementing a binary tree root = Node(0) root.left = Node(1) root.right = Node(2) root.left.left = Node(3) root.left.right = Node(4) root.right.right = Node(5) root.left.right.left = Node(6) root.right.right.left = Node(7) x = int(input("Enter ancestor node: ")) y = int(input("Enter descendant node: ")) ancestors(root,y) if(x in l): print("Yes") else: print("No")




Output:
Enter ancestor node: 1
Enter descendant node: 6
Yes

Enter ancestor node: 1
Enter descendant node: 7
No


More Articles of Deep Gandhi:

Name Views Likes
Python program to construct all possible binary search trees for keys 1 to N 474 18
Python Requests Making a request 469 15
Python Requests Retrieving Content 452 18
Python Requests Getting Headers 448 13
Python Requests Response Status Codes 599 14
Python program to add a new page after a particular page 506 19
Python Requests Complicated POST Requests 608 13
Python program to find inorder predecessor for a given key in binary search tree with recursion 628 17
Python program to find second largest element in binary search tree 805 14
Introduction to Requests (A module of Python) 533 21
Python program to append two dictionaries 459 15
Python program to convert an image to pdf file 519 18
Python Requests Adding Custom Headers 615 13
Python How to find an element in Tuple by value 466 15
Python program to find inorder predecessor and successor for a given key in binary search tree with recursion 880 21
Python program to find height of binary tree represented by parent array 619 20
Python program to query for ancestor-descendant relationship in a tree 1136 25
Python Requests Passing Parameters in URLs 2145 16
Python program to print common nodes on path from root 507 15

Comments