Q 2 ( 5 0 points ) Find a path between two nodes in a binary search tree Implement function find path ( element 1 key, element 2 key ) The function takes two keys as input and returns the path between the corresponding two nodes ( including both ends ) In case of either key does not exist, return an empty list You must use TreeNode object from tree node py You are not allowed to change tree node py Class TreeNode def init ( self , key, val, left None, right None, parent None ) self key key self payload val self leftChild left self rightChild right self parent parent def hasLeftChild ( self ) return self leftChild def hasRightChild ( self ) return self rightChild def str ( self ) return ' ( ' str ( self key ) ' , ' str ( self payload ) ' ) ' Below is the template for Question 2 UMass ECE 2 4 1 Advanced Programming Homework 3 Fall 2 0 2 4 question 2 py Binary Search Tree from tree node import TreeNode class BinarySearchTree def init ( self ) self root None def put ( self , key, val ) if self root self put ( key , val, self root ) else self root TreeNode ( key , val ) def put ( self , key, val, node ) if key node key if node hasLeftChild ( ) self put ( key , val, node leftChild ) else node leftChild TreeNode ( key , val, parent node ) else if node hasRightChild ( ) self put ( key , val, node rightChild ) else node rightChild TreeNode ( key , val, parent node ) def setitem ( self , k , v ) self put ( k , v ) def get ( self , key ) res self get ( key , self root ) if res is None return None return res def get ( self , key, node ) if node is None return None if node key key return node if key node key return self get ( key , node leftChild ) else return self get ( key , node rightChild ) def getitem ( self , key ) return self get ( key ) def find path ( self , element 1 key, element 2 key ) TODO Fill in this function to get a path from element 1 to element 2 pass def main ( ) mytree BinarySearchTree ( ) mytree 4 red mytree 8 yellow mytree 6 blue mytree 3 pew print ( mytree 6 ) print ( mytree 2 ) path mytree find path ( 3 , 8 ) for i , node in enumerate ( path ) print ( node , end ' ' if i len ( path ) 1 else ' ' ) if name main main ( )

Question

Q 2 ( 5 0 points )   Find a path between two nodes in a binary search tree  Implement function find   path ( element   1   key, element   2   key )   The function takes two keys as input and returns the path between the corresponding two nodes ( including both ends )   In case of either key does not exist, return an empty list  You must use TreeNode object from tree   node py   You are not allowed to change tree   node py   Class TreeNode  def     init     ( self , key, val, left   None, right   None, parent   None )   self key   key self payload   val self leftChild   left self rightChild   right self parent   parent def hasLeftChild ( self )   return self leftChild def hasRightChild ( self )   return self rightChild def     str     ( self )   return ' ( '   str ( self   key )   ' , '   str ( self   payload )   ' ) ' Below is the template for Question 2       UMass ECE 2 4 1   Advanced Programming Homework   3   Fall 2 0 2 4 question 2   py   Binary Search Tree       from tree   node import TreeNode class BinarySearchTree  def     init     ( self )   self root   None def put ( self , key, val )   if self root  self    put ( key , val, self root ) else  self root   TreeNode ( key , val ) def   put ( self , key, val, node )   if key   node key  if node hasLeftChild ( )   self    put ( key , val, node leftChild ) else  node leftChild   TreeNode ( key , val, parent   node ) else  if node hasRightChild ( )   self    put ( key , val, node rightChild ) else  node rightChild   TreeNode ( key , val, parent   node ) def     setitem     ( self , k , v )   self put ( k , v ) def get ( self , key )   res   self    get ( key , self root ) if res is None  return None return res def   get ( self , key, node )   if node is None  return None if node key     key  return node if key   node key  return self    get ( key , node leftChild ) else  return self    get ( key , node rightChild ) def     getitem     ( self , key )   return self get ( key ) def find   path ( self , element   1   key, element   2   key )         TODO  Fill in this function to get a path from element   1 to element   2       pass def main ( )   mytree   BinarySearchTree ( ) mytree   4      red  mytree   8      yellow  mytree   6      blue  mytree   3      pew  print ( mytree   6   ) print ( mytree   2   ) path   mytree find   path ( 3 , 8 ) for i , node in enumerate ( path )   print ( node , end   '       ' if i   len ( path )   1 else ' ' ) if     name               main         main ( )

SolutionInn · Accepted Answer

The Answer is in the image, click to view ...

Question: Q 2 ( 5 0 points ) . Find a path between two nodes in a binary search tree. Implement function find _ path (

Step by Step Solution

Students Have Also Explored These Related Programming Questions!