# Binary Search Tree Traversals

`# Implement binary search tree insert method# Creating a class of nodeclass Node(object):    def __init__(self):        self.left = None        self.right = None        self.data = None# Inserting a node in BSTdef insertion(val):    # if first node it will be considered as a root    if (root.data == None):        print(val, " Inserted as root")        root.data = val    # else executed for all the other insertions    else:        # Pointer to move around tree to search for a place for new node        p = root        # Creating a new node        n = Node()        n.data = val        # Iterating to search for an appropriate place in the new node        while (1):            # if val is less than the current node p indicates that new node will be inserted on left subtree            if (val < p.data):                if (p.left == None):                    print(val, " Inserted on left of ", p.data)                    p.left = n                    break                else:                    p = p.left            # if val is greater than the current node p indicates that new node will be inserted on right subtree            else:                if (p.right == None):                    print(val, " Inserted on right of", p.data)                    p.right = n                    break                else:                    p = p.rightdef inorder(node):    if node:   # Traverse left subtree        inorder(node.left)   # Visit node        print(node.data)   # Traverse right subtree        inorder(node.right)# A function to do preorder tree traversaldef printPreorder(root):    if root:        # First print the data of node        print(root.data),        # Then recur on left child        printPreorder(root.left)        # Finally recur on right child        printPreorder(root.right)def printPostorder(root):    if root:        # First recur on left child        printPostorder(root.left)        # the recur on right child        printPostorder(root.right)        # now print the data of node        print(root.data)root = Node()#print("Value ", deletion(25), "deleted successfully")#print("Value ", deletion(10), "deleted successfully")root = Node()insertion(27)insertion(5)insertion(12)insertion(85)insertion(6)insertion(19)insertion(1)insertion(8)insertion(95)insertion(3)print("In order:")inorder(root)print("Pre order:")printPreorder(root)print("Post order:")printPostorder(root)Screenshots:https://ibb.co/M7M30wxhttps://ibb.co/wzD5FkVTime complexityi. Best case scenario: In the event that the root node is selected as the nodeto be searched, just one comparison will need to be made, resulting in aconstant duration. In the best situation, time complexity would be O. (1).ii. The average case: When a binary search tree is balanced(a binary search tree is considered balanced if the height difference between nodes onthe left and right subtrees is not greater than one), height is logN, where N is thenumber of nodes in the tree.The time it takes to search for a key in a binary search tree is equal to the height ofthe tree, which is logN, so the time complexity for searching is O(logN) in the averagecase. During the search operation, we will continue to traverse through nodes one at atime. Suppose we find the element in the second level, in which case we have performedtwo comparisons. If we get the element in the third level, we will be performing threecomparisons.Worst-case scenario: If the binary search tree is imbalanced or distorted(skewed binary search tree is a tree in which there are no nodes available in leftsubtree or right subtree see the image below to get better understanding)Space complexity: Since there are a maximum of n stack frames that may be held inmemory at any given moment, the space cost of searching a node in a BST would be O(n),where n is the depth of the tree (number of nodes present in a tree).A single exploration of every node in the tree is known as tree traversal.In-order traversal can be implemented either iteratively or recursively. Recursion isthe method we're interested in using, though. When traversing a tree in order, theleft child is explored first, followed by the root then the right child.In light of this, the following stages will be used to implement a recursive procedure:Visit the left subtree repeatedlyGo to the node.Continually go to the appropriate subtreeA point between the recursive traversals of the left and right subtrees is visitedduring an inorder traversal. A binary tree T's inorder traversal can be thought of asgoing "from left to right" across its nodes.Pre-order traversal involves the following tree exploration:Go to the node.Investigate the left subtree repeatedlyInvestigate the appropriate subtree repeatedlyWe only need to reverse the visit order in postorder traversal; the method isillustrated as follows:Visit the left subtree repeatedlyContinually go to the appropriate subtreeGo to the node.`

(Time and Space Complexity of Binary Search Tree (BST), 2021; Tree Traversals (Inorder, Preorder and Postorder), 2009)

References

Time and Space complexity of Binary Search Tree (BST). (2021, December 29). OpenGenus IQ: Computing Expertise & Legacy. https://iq.opengenus.org/time-and-space-complexity-of-binary-search-tree/

Tree Traversals (Inorder, Preorder and Postorder). (2009, June 23). GeeksforGeeks. https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/