**** IN PYTHON PLEASE BSTGetHeight and BSTPrintInorder need to be modified to be non recursive or iterative methods ****

[answerhappygod]

****
IN PYTHON PLEASE
BSTGetHeight and BSTPrintInorder need to be modified to be
non recursive or iterative methods
****

In Python Please Bstgetheight And Bstprintinorder Need To Be Modified To Be Non Recursive Or Iterative Methods 1 (196.48 KiB) Viewed 31 times

1 from TreePrint import pretty_tree 2 3 class BinarySearchTree: 4 # Constructor just assigns an empty root. definit__(self): 5 6 self.root = None 7 8- def BSTGetHeight(self, node): if node is None: 9 10 return -1 11- else: 12 13 leftHeight = self.BSTGetHeight(node.left) rightHeight = self. BSTGetHeight(node.right) return 1 + max(leftHeight, rightHeight) 14 15 16 def BSTPrintInorder(self, node): if node is None: 17 18 return 19 else: 20 self. BSTPrintInorder (node.left) print(node.key, end=" ") 21 22 self. BSTPrintInorder(node.right) 23 24 25 # Search for a node containing a matching key. Returns the # Node object that has the matching key if found, None if # not found. 26 27 def search(self, desired_key): 28 current_node = self.root 29 - while current_node is not None: 30 # Return the node if the key matches. if current_node.key=desired_key: 31 32 return current_node 33 34 # Navigate to the left if the search key is # less than the node's key. 35 36 elif desired_key < current_node.key: 37 current_node = current_node.left 38 39 40 # Navigate to the right if the search key is #greater than the node's key. else: 41 42 current_node = current_node.right 43 44 # The key was not found in the tree. return None 45 46 47 # Inserts the new node into the tree. def insert(self, node): 48-
49 50 51 52 53 - 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76- 77 78 79 80 81 82 83 84- 85 86 87 88 89 90 91 92 93 94 95 96 - # Check if the tree is empty if self.root is None: self.root node else: current_node = self.root while current_node is not None: if node.key < current_node.key: # If there is no left child, add the new #node here; otherwise repeat from the #left child. if current_node.left is None: current_node.left= node current_node = None else: current_node = current_node.left else: # If there is no right child, add the new #node here; otherwise repeat from the #right child. if current_node.right is None: current_node.right = node current_node = None else: current_node = current_node.right # Removes the node with the matching key from the tree. def remove(self, key): parent None current_node = self.root # Search for the node. while current_node is not None: # Check if current_node has a matching key. if current_node.key == key: if current_node.left is None and current_node.right is None: # if parent is None: # Node is root self.root None elif parent.left is current_node: parent.left = None else: parent.right = None return # Node found and removed elif current_node.left is not None and current_node.right is None if parent is None: # Node is root self.root = current_node.left elif parent.left is current_node:
97 98 - 99 100 101 - 102 - 103 104- 105 106- 107 108 109- 110 111 112- 113 114 115 116 117 118 119 120 121- 122 123 124 125 126 127 128 129 - 130 131 parent.left = current_node.left else: parent.right = current_node.left return # Node found and removed elif current_node.left is None and current_node.right is not Non if parent is None: #Node is root. self.root = current_node.right elif parent.left is current_node: parent.left= current_node.right else: parent.right = current_node.right return # Node found and removed else: # Case 3 # Find successor (leftmost child of right subtree) successor = current_node.right while successor.left is not None: successor = successor.left current_node.key= successor.key parent current_node current_node = current_node.right key = parent.key elif current_node.key < key: # Search right parent current_node current_node = current_node.right else: # Search left parent = current_node current_node = current_node.left return # Node not found # Build a string representation of the tree by #getting the string representation of the root. def_str__(self): return pretty_tree(self) # Copy successor to cu # Remove successor frc # Loop continues with