Python 3.3+ Immutable Binary Search Tree (unbalanced) < 25 Lines of Code

I was Thinking of uses for the yield from statement (available since Python 3.3), and I thought of doing a in-order recursive traversal of a binary search tree.

While on the way I wrote a less than 25 line immutable binary search tree implementation that is function based and though it would be good to share it with you.

Immutable here means that any other thread or co routine that has the tree, can reference it without it changing.

Since insertion create a new tree that shared all unchanged parts of the original tree. The tree is a recursive structure of nodes that contain other nodes. Each node can have a sub tree under it.

Calls for inserting a new value or searching The code works as as follows:

tree = None	-- before you start with any values set your variable for the tree to None (you could call it mytree or anything other than tree)
tree = insert(tree, value)	-- call insert with your tree variable and it will return a new tree value.
if contains(tree, value):      ...	-- call contains to check if value is in tree
in_order(tree)	--returns a generator to sequence through all values in sorted order

i.e.

for value in in_order(tree):     print(item)

or

print(list(in_order(tree))  -- convert generator to list to print

---

Here is the complete code from my gist site:

	# bst.py immutable Binary search tree (not balanced)
	# using 'yield from' new in python 3.3
	# start with tree = None
	# nodes are a list of [value, left_tree, right_tree]
	# every node is a subtree, so tree argument is a tree or subtree
	def insert(tree, value):
	""" creates tree if tree is None, returns new tree"""
	if not tree:
	return (value, None, None) # top of tree
	if value < tree[0]:
	return (tree[0], insert(tree[1], value), tree[2]) # add to left
	else:
	return (tree[0], tree[1], insert(tree[2], value)) # add to right
	def contains(tree, value):
	"""tree is existing tree or node(subtree)"""
	if not tree:
	return False
	if value == tree[0]: # found it
	return True
	if value < tree[0]: # desend lookiing down left or right
	return contains(tree[1], value)
	else:
	return contains(tree[2], value)
	def in_order(tree):
	"""generate inorder sequence: tree is existing tree or node(subtree)"""
	if(tree):
	yield from in_order(tree[1])
	yield tree[0]
	yield from in_order(tree[2])
	def test():
	items = ( 1, 5, 7, 2, 4, 9, 3, 12, 6, -4, 11, 22, 100, 4, 2)
	t = None
	for x in items: # build tree
	t = insert(t, x)
	assert(list(in_order(t)) == sorted(items)) # print in order
	assert(contains(t, 4) == True)
	assert(contains(t, 8) == False)
	if __name__ == '__main__':
	test()
	print('testing done')

view raw bst.py hosted with ❤ by GitHub

Enjoy! If you have any ideas for future blogs or videos or want to contact me, go to contact form