# Binary Search Tree Traversals

4 min readOct 14, 2022

--

# 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/wzD5FkVTime complexity

i. 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 repeatedly

Go to the node.

Continually go to the appropriate subtree

A 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 repeatedly

Investigate the appropriate subtree repeatedly

We only need to reverse the visit order in postorder traversal; the method isillustrated 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/**