Tips/tricks related to Computer Graphics, GPUs and other programming

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.

Advertisements

Comments on: "Binary Search Tree in Python" (1)

  1. The code is good but it is more appreciable that if done using GUI or tk-inter.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: