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 break if current_node.right is None: current_node.right = node break nodes_found.append(current_node.left) nodes_found.append(current_node.right)
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: return if root.left is not None: display_nodes(root.left) print(root.key, end=' ') if root.right is not None: display_nodes(root.right)
Here is a Python script that displays the nodes of the binary search tree created above.
display_nodes(root) 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!