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: Enjoy! If you have any ideas for future blogs or videos or want to contact me, go to contact form