Binary Search Tree Traversals

# Implement binary search tree insert method
# Creating a class of node
class Node(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None


# Inserting a node in BST
def 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.right

def 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 traversal
def 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/M7M30wx
https://ibb.co/wzD5FkV
Time complexity

i. Best case scenario: In the event that the root node is selected as the node
to be searched, just one comparison will need to be made, resulting in a
constant 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 on
the left and right subtrees is not greater than one), height is logN, where N is the
number of nodes in the tree.
The time it takes to search for a key in a binary search tree is equal to the height of
the tree, which is logN, so the time complexity for searching is O(logN) in the average
case. During the search operation, we will continue to traverse through nodes one at a
time. Suppose we find the element in the second level, in which case we have performed
two comparisons. If we get the element in the third level, we will be performing three
comparisons.
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 left
subtree 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 in
memory 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 is
the method we're interested in using, though. When traversing a tree in order, the
left 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 repeatedly
Go to the node.
Continually go to the appropriate subtree

A point between the recursive traversals of the left and right subtrees is visited
during an inorder traversal. A binary tree T's inorder traversal can be thought of as
going "from left to right" across its nodes.
Pre-order traversal involves the following tree exploration:

Go to the node.
Investigate the left subtree repeatedly
Investigate the appropriate subtree repeatedly

We only need to reverse the visit order in postorder traversal; the method is
illustrated as follows:

Visit the left subtree repeatedly
Continually go to the appropriate subtree
Go 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/