Question

PYTHON CODING

Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary Search Tree in ascending or deceasing order. The order type is an input to the method and can be "ascending" or "descending". The ascending input would return the node values of the tree beginning with the smallest and ending with the largest, descending returns the opposite. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.Illustrate the performance of the sortTraversal method

class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
  
class BSTree():
def __init__(self, rootdata):
self.root = Node(rootdata)
  
def insert(self, data, cur_node):
if data < cur_node.data:
if cur_node.left == None:
cur_node.left = Node(data)
else:
self.insert(data, cur_node.left)
  
elif data > cur_node.data:
if cur_node.right == None:
cur_node.right = Node(data)
else:
self.insert(data, cur_node.right)
else:
print("Duplicate value!")

Answer 1

# Welcome to sorted BST tree traversal code using Python 3

class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.data = key

/* We are using Node class to initialize the attributes of each node
 init method is a constructor here.
 Constructors are used to initialize the state of the object.
*/

class BSTree():
    def __init__(self, rootdata):
        self.root = Node(rootdata)

/* Above class BSTree is used to initialize the root node, the constructor inside is calling "Node" class and that will instantiate an object of type "Node" with rootdata as node data and left and right attributes with None
*/

def insert(data, cur_node):
    if data < cur_node.data:
        if cur_node.left == None:
            cur_node.left = Node(data)
        else:
            insert(data, cur_node.left)
    elif data > cur_node.data:
        if cur_node.right == None:
            cur_node.right = Node(data)
        else:
            insert(data, cur_node.right)
    else:
        print("Duplicate value!")

/* Above method will insert data by comparing the values with the current node value, if the new value is smaller than the current node it will try to insert the new data to its left. If left attribute of current node is None, it will insert the new node there else it will invoke a recursive call to same method with left of current node as current node value.

Similarly, if the new node value is greater than the current node value it will try to insert the new data to its right. If right attribute of current node is None, it will insert the new node there else it will invoke a recursive call to same method with right of current node as current node value.

*/

def sortTraversal(root,ordering):
    if ordering=='ascending':
        if root:
            sortTraversal(root.left,ordering)
            print(root.data)
            sortTraversal(root.right,ordering)
    elif ordering=='descending':
        if root:
            sortTraversal(root.right,ordering)
            print(root.data)
            sortTraversal(root.left,ordering)
​​​​​​​
/* Above method is used to print the BST in sorted order based on input. Method includes if-else block that will be printing the data based on 'ordering' value input.

If input is 'ascending' it will start with the leftmost node, covers the left subtree first, followed by root and finally the right subtree.
This method of traversal is also called Inorder traversal.

If input is 'descending', it will start in reverse way, it will start with rightmost node of tree, covers the right subtree, followed by root and then left subtree.
*/


if __name__ == '__main__':
    t=BSTree(10)
    arr=[5,2,3,1,7,13,12,15]
    for i in arr:
        insert(i,t.root)
    order = input("Please choose sorting order ascending/descending: ")
    sortTraversal(t.root,order)

/* In the above main() method, we are instantiating an object of BSTree class and it will initialize the root node with 10 as data value.
We are using an array to insert data in BST using insert method with array elements(i) and root node(t.root) as parameters.
Once BST is generated, we are taking user input for sorting order and then calling sortTraversal with root node and order values as parameters
*/ 

BST tree traversal needs to go through each and every node of the tree and in that case we can call the time complexity will be minimum of O(n).