Binary Search Tree in Python

It has been a while since I have written a data structure from scratch (had to write B-Trees for an Advanced Data Structures course 2 years ago), so I decided to refresh my memory by quickly writing up Binary Search Trees in Python. Making sure you are familiar with data structures always helps with interviews too.

You can access the file here. I have only tested this for integers, so might need a little bit of work for other data types. The following methods have been implemented:

• add(data)
• remove(data)

Traversals:

• preorder()
• inorder()
• postorder()
• bfTraversal() (Breadth-first traversal)

Helper methods:

• isLeaf(node) – checks if a node is a leaf
• lcAncestor(value1, value2) – finds the least common ancestor of two nodes with values value1 and value2
• printAllPaths() – prints all the possible paths from the root to the leaves

I won’t go over how a BST works, but hopefully the code is self-explanatory.

If there are any questions let me know – hope people find it useful.

Advertisement