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

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 Insertion

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:

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:

1. Traverse the left sub tree recursively
2. Get the data of the current node
3. 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

The code is implemented and the method is called as follows:

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())

The 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:

1. Get the data of the current node
2. Traverse the left sub tree recursively
3. Traverse the right sub tree recursively

Implementation follows:

#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

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:

1. Traverse the left sub tree recursively
2. Traverse the right sub tree recursively and
3. 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

Short Representation of Input and Output:

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

Binary Search Tree for values 15, 10, 4, 12, 35, 90, 25, 30

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

Originally published at https://www.numpyninja.com on August 19, 2020.