# How to Implement Binary Search Tree(BST) and the Traversals with and without Recursion in Python?

*What is a Binary Search Tree?*

Binary Search Tree is a tree based Data Structure which has the following constraints:

Â· Each node can have at most two children: Left-child, Right-child

Â· Left- child store value lesser than the root node

Â· Right- child store value greater than the root node.

Â· No duplicate values can be stored in a Binary Search Tree

*How to create a binary search tree?*

Let us consider an example to create a Binary Search Tree.

Create a Binary Search Tree using the following values:

15, 10, 4, 12, 35, 90, 25, 30

The steps involved are as follows:

First, create a root node ,here it is 15 . Then insert the value 10. 10 is lesser than 15. So it becomes the left child of 15. Now, insert the value 4. Obviously 4 is lesser than 15. 4 goes left of 15. But 15 already has 10 as a child node. So, now compare 4 with 10. 4 is lesser than 10 4 becomes left child of 10 since there is no left child exists for 10. Then, insert the value 12 which becomes the right child of 10. Then comes 35 which is greater than 15. So 35 goes right of 15. Similarly insert 25 and 90 which is clearly illustrated in the diagram below:

*Binary Search Tree Implementation:*

```
# Implementation of Binary Search Tree in Python
# Define a Tree Structure:
class BinarySearchTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Adding nodes otherwise called insertion
def insert(self, data):
# Binary Search Tree cannot have duplicate values condition
if data == self.data:
return
if data < self.data:
# Check if there is a value in the left node,then
# call the method recursively
if self.left:
self.left.insert(data)
else:
self.left = BinarySearchTreeNode(data)
else:
# Check if there is a value in the right node,then
# call the method recursively
if self.right:
self.right.insert(data)
else:
self.right = BinarySearchTreeNode(data)
tree_elements = [15, 10, 4, 12, 35, 90, 25, 30]
root = BinarySearchTreeNode(tree_elements[0])
for i in range(1, len(tree_elements)):
root.insert(tree_elements[i])
```

Now , we created a Binary Search Tree. Let us take a look at how to do Traversals in a Binary Search Tree. What is a Tree Traversal? A Tree Traversal is nothing but visiting each node in a tree exactly once. Here we are discussing the three major Depth First Tree Traversal Techniques:

In-Order Traversal --> Right, Root, Left

Pre-Order Traversal--> Root, Left, Right

Post-Order Traversal--> Left, Right, Root

*In- Order Traversal:*

The name In-Order itself denotes that the nodes are visited in the order Left , Root, Right. Root is visited in- between Left and Right node/sub tree. Usually, In order Traversal will give a sorted value output. Here the steps are as follows:

Traverse the left sub tree recursively

Get the data of the current node

Traverse the right sub tree recursively

```
# Implement In-order Traversal using Recursion
def inorder_traversal(self):
# Need to return the elements in an order Left,Right,Root
# Create a list for elements to store retrieved values
elements = []
# visit Left Tree first
if self.left:
elements += self.left.inorder_traversal()
# visit root node
elements.append(self.data)
# visit right Tree
if self.right:
elements += self.right.inorder_traversal()
return elements
```

*In-Order Traversal without recursion/Iterative Method:*

In this iterative method, its quite easy to use the concept of stack. In this method, traverse down the tree pushing each left node into the stack until no more left child. Then, get each node from the stack and add it to the visited node list and append right nodes to the stack. In the next iteration the right node will become the root of the sub tree and the process repeats until all nodes from the stack are popped out

```
# Implementation of in-order traversal without using recursion
def in_order_no_recursion(self):
# Initialize a stack
stack = []
# Initialize a list to store visited nodes
elements = []
# Initialize current node to root
current = self
# Loop until all the nodes are visited
while current or stack:
# If current node ,then push it in the stack and assign current to left node
if current:
stack.append(current)
current = current.left
# If current is none, pop the value and append it to the node visited
else:
current = stack.pop()
elements.append(current.data)
# Now get the right node
current = current.right
return elements
```

```
tree_elements = [15, 10, 4, 12, 35, 90, 25, 30]
root = BinarySearchTreeNode(tree_elements[0])
for i in range(1, len(tree_elements)):
root.insert(tree_elements[i])
print(root.inorder_traversal())
print(root.in_order_no_recursion())
```

`Output will be: [4, 10, 12, 15, 25, 30, 35, 90]`

*Pre- Order Traversal:*

Like the name pre-order, here the nodes are visited in the order Root,Left, Right. Root is visited before Left and Right Nodes/ sub tree. Hence the steps are as follows:

Get the data of the current node

Traverse the left sub tree recursively

Traverse the right sub tree recursively

```
#Implementation of Pre-Order traversal with Recursion
def pre_order_traversal(self):
# Need to return the elements in an order Root, Left, Right
# Create a list of elements to store the retrieved data
elements = [self.data]
if self.left:
elements += self.left.pre_order_traversal()
if self.right:
elements += self.right.pre_order_traversal()
return elements
```

*Pre-Order Traversal without Recursion:*

In this iterative method, first push the root node into the stack. Starting from the root, each visited node is added to the list . At the same time, each right and left nodes are pushed into the stack if found in the order , right node first and left next so that when popped out of the stack, the nodes can be obtained in correct order, say left sub tree first and then right sub tree

```
# Implementation of pre-order traversal without recursion
def pre_order_no_recursion(self):
# Initialize stack to root
stack = [self]
# Initialize an list for visited nodes
elements = []
# Loop until stack is empty
while stack:
# Take the root node
current = stack.pop()
# Add to visited node
elements.append(current.data)
# If there is a right child, append it to the stack to visit
if current.right:
stack.append(current.right)
# If there is left child, append it to the stack to visit
if current.left:
stack.append(current.left)
return elements
```

```
tree_elements = [15, 10, 4, 12, 35, 90, 25, 30]
root = BinarySearchTreeNode(tree_elements[0])
for i in range(1, len(tree_elements)):
root.insert(tree_elements[i])
print(root.pre_order_traversal())
print(root.pre_order_no_recursion())
```

`Output will be: [15, 10, 4, 12, 35, 25, 30, 90]`

*Post- Order Traversal:*

In Post-Order Traversal, the nodes are visited in the order Left, Right, Root. Root is visited post Left and Right Node visits. Hence the steps are as follows:

Traverse the left sub tree recursively

Traverse the right sub tree recursively and

Get the data from the node

```
# Implementation of Post-Order traversal using Recursion
def postorder_traversal(self):
# Need to return the elements in an order Left,Right,Root
elements = []
if self.left:
elements += self.left.postorder_traversal()
if self.right:
elements += self.right.postorder_traversal()
elements.append(self.data)
return elements
```

*Post-Order Traversal without recursion:*

The same stack concept is used here to implement post- order traversal iterative method. First, the stack is initialized to root , then each time a node is encountered , the value will be added to the visited list and the left and right nodes are appended into the stack. In this method the visited nodes are appended in reverse order, popping the values out from the visited node list will give the post-order traversal output.

```
# Implementation of post-order traversal without recursion
def postorder_no_recursion(self):
elements = []
# Create an empty list and assign root
stack = [self]
# Create another list to store visited nodes
out = []
# Loop till stack is empty
while stack:
# Take the last element in the stack
current = stack.pop()
# Add it to visited node
out.append(current.data)
# Append left child of the current node to the stack
if current.left:
stack.append(current.left)
# Append right child if found
if current.right:
stack.append(current.right)
# Pop out the elements in the stack for post order format
while out:
elements.append(out.pop())
return elements
```

```
tree_elements = [15, 10, 4, 12, 35, 90, 25, 30]
root = BinarySearchTreeNode(tree_elements[0])
for i in range(1, len(tree_elements)):
root.insert(tree_elements[i])
print(root.postorder_traversal())
print(root.postorder_no_recursion())
```

`Output will be:[4, 12, 10, 30, 25, 90, 35, 15]`

*Short Representation of Input and Output :*

* Input:* 15, 10, 4, 12, 35, 90, 25, 30

*Output:*

After In Order Traversal: 4, 10, 12, 15, 25 , 30, 35, 90

After Pre Order Traversal: 15, 10, 4, 12, 35, 25, 30, 90

After Post Order Traversal: 4, 12, 10, 30, 25, 90, 35, 15