Inorder Traversal of Binary Search Tree in Python

Inorder Traversal of Binary Search Tree in Python

In addition to taking courses on Python, computer science, data structures, and algorithms, I have joined a few communities offering programming challenges to help me improve my coding skills. I enjoy these programming challenges, and recently finished the 30 Days of Code Challenge at HackerRank using both C# and Python.

One of the recent challenges I received was to code the inorder traversal of a binary search tree. The binary search tree was already created and I just needed to print all the nodes in correct order, which means I had to do a proper inorder traversal of the binary search tree and print the key of each node along the way.

Create Binary Search Tree in Python

First things first, I need a binary search tree in Python. Here is a barebones Node Class in Python along with a simple add function that will create a binary tree using level-order traversal.

from collections import deque

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def add(node, root):
    if root is None:
        raise ValueError('root cannot be None.')

    nodes_found = deque([root])

    while len(nodes_found) > 0:
        current_node = nodes_found.popleft()

        if current_node.left is None:
            current_node.left = node
        if current_node.right is None:
            current_node.right = node


I can create a balanced, binary search tree using keys 1 - 15 using a simple script in Python.

root = Node(8)
keys = [4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]

for key in keys:
    add(Node(key), root)

I am essentially doing a level-order traversal (like breadth-first search) that adds these keys in a particular order to create a binary search tree. The order of the keys in the list is important.

Inorder Traversal of Binary Search Tree

Now that I have a binary search tree in Python, I need to perform an inorder traveral of the nodes to display the keys in their correct order. An inorder traveral will display a node's left sub-tree, then the value of its key, followed by the right sub-tree. An inorder traversal makes the most sense for binary search trees, because this is exactly the way binary search trees are ordered.

Here is a display_nodes Python function that displays each key of a binary search tree using inorder traversal.

def display_nodes(root):
    if root is None:

    if root.left is not None:

    print(root.key, end=' ')

    if root.right is not None:

Here is a Python script that displays the nodes of the binary search tree created above.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 


In the programming challenge the binary search tree was already provided, so the code I wrote to create the binary search tree wasn't part of the challenge. I just wrote that really quickly in Python to set up the challenge. The only code I needed to write in Python ( I did it in C# as well ) was the display_nodes function, which is a recursive function that does an inorder traveral of the binary search tree. This challenge didn't take me long, but it's great to have these challenges to keep binary search trees fresh in my mind. As a freelance ASP.NET C# Web Developer I don't come across binary search trees in my daily development.

Hope this helps!

Posted by David Hayden
Koder Dojo
David Hayden is a professional Microsoft web developer. He mentors and tutors computer science students in C, C++, Java, and Python. In addition to writing computer science and programming tutorials at Koder Dojo, he also writes tutorials on C#, ASP.NET Core, and Azure as well as tutorials on Orchard Core.