Python program to print path from root to a given node in a binary tree














































Python program to print path from root to a given node in a binary tree



# Python program to print path from root to a given node in a binary tree

# to print path from root to a given node
# first we append a node in array ,if it lies in the path 
# and print the array at last


# creating a new node
class new_node(object):
def __init__(self,value):
self.value=value
self.left=None
self.right=None

class Root_To_Node(object):
def __init__(self,root):
self.root=root


# function to check if current node in traversal 
# lies in path from root to a given node
# if yes then add this node to path_array
def check_path(self,root,key,path_array):
#base case
if root==None:
return False

# append current node in path_array
# if it does not lie in path then we will remove it.
path_array.append(root.value)
if root.value==key:
return True

if (root.left!=None and self.check_path(root.left,key,path_array)) or (root.right!=None and self.check_path(root.right,key,path_array)):
return True

#  if given key does not present in left or right subtree rooted at current node
#  then delete current node from array
# and return false

path_array.pop()
return False

def Print_Path(self,key):
path_array=[]
check=self.check_path(self.root,key,path_array)
if check:
return path_array
else:
return -1
if __name__=="__main__":
root=new_node(5)
root.left=new_node(2)
root.right=new_node(12)
root.left.left=new_node(1)
root.left.right=new_node(3)
root.right.left=new_node(9)
root.right.right=new_node(21)
root.right.right.left=new_node(19)
root.right.right.right=new_node(25)
obj=Root_To_Node(root)
key=int(input())
x=obj.Print_Path(key)
if x==-1:
print("node is not present in given tree")
else:
print(*x)
''' since we are going at each node only ones
   so time complexity of above algorithm is O(n)
   where n= no of nodes in the tree'''

More Articles of Saurabh Sisodia:

Name Views Likes
Python Imaging Library(ExifTags Module) 413 13
Python Imaging Library(ImageTk Module) 579 20
Python Imaging Library(ImageStat Module) 560 29
Python Imaging Library(ImageSequence Module) 428 25
Python Imaging Library(ImagePath Module) 467 28
Python Imaging Library(ImageMath Module) 326 20
Python Imaging Library(ImageFont Module) 617 27
Python Imaging Library(ImageFilter Module) 472 21
Python Imaging Library(ImageFile Module) 323 11
Python Imaging Library(ImageEnhance Module) 364 12
Python program to check if a binary tree is subtree of another binary tree 598 14
Python Imaging Library(ImageDraw Module) 442 22
Python Imaging Library(ImageColor Module) 358 17
Python Imaging Library(Image Module) 404 20
Introduction Of Python Imaging Library (Pillow) 452 25
Python program to reverse a path in binary search tree using queue 423 19
Python program to find the maximum sum leaf to root path in a binary tree 434 27
Python program to find sum of all the numbers that are formed from root to leaf paths 315 11
Python program to find sum of leaf nodes at minimum level 344 16
Python program to print the path common to the two paths from the root to the two given nodes 390 20
Python program to find if there is a triplet in a Balanced binary search tree that adds to zero 466 14
Python program to find longest path with same values in a binary tree 385 14
Python program to find longest consecutive sequence in binary tree 448 27
Python program to find number of turns to reach from one node to other in binary tree 373 25
Python program to find the closest leaf in a binary tree 450 22
Python Program to find the closest leaf node to a given node 392 16
Python program to count pairs from two binary search trees whose sum is equal to a given value x 347 24
Python program to find pairs with given sum such that pair elements lie in different binary search trees 369 22
Python program to check whether a binary tree is a full binary tree or not without using recursion 283 15
Python program to find difference between sums of odd level and even level nodes of a binary tree 331 17
Python program to print duplicate elements from the binary search tree 337 15
Python program to print middle level of perfect binary tree without finding height 381 20
Python program to print path from root to a given node in a binary tree 858 23
Python program to find distance between two given keys of a binary tree 326 15
Python program to find distance from root to given node in a binary tree 320 15
Python program to check if given sorted sub-sequence exists in binary search tree 257 11
Python program to find kth ancestor of a node in binary tree 339 20
Python program to print ancestors of a given node in binary tree 430 22
Python program to find sum of value in each level of binary tree 386 16
Python program to check if a binary tree is sorted level-wise or not 328 14
Python program to get level of a node in binary tree using recursion 362 15
Python program to find successor for a given key in binary search tree without recursion 330 13
Python program to find k-th smallest element in binary search tree 353 24
Python program to convert binary tree to binary search tree 352 16
Python program to check if a binary tree has duplicate values 688 24

Comments