Binary Search Tree Traversals

Mohammad M Rahman
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/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 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 visited
during 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 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/

--

--

Mohammad M Rahman

Research interest: Islam, Computer science, Psychology/Sociology. Please see my profile links for further info.