represent binary search trees in python

Question

how do i represent binary search trees in python?

• David Z: Can you be more specific? What are you trying to do?
• Bunny Rabbit: I am trying to build a binary search trees for the sake of learning.

Answer 1

class Node(object):
 def __init__(self, payload):
 self.payload = payload
 self.left = self.right = 0
 # this concludes the "how to represent" asked in the question. Once you
 # represent a BST tree like this, you can of course add a variety of
 # methods to modify it, "walk" over it, and so forth, such as:
 def insert(self, othernode):
 "Insert Node `othernode` under Node `self`."
 if self.payload <= othernode.payload:
 if self.left: self.left.insert(othernode)
 else: self.left = othernode
 else:
 if self.right: self.right.insert(othernode)
 else: self.right = othernode
 def inorderwalk(self):
 "Yield this Node and all under it in increasing-payload order."
 if self.left:
 for x in self.left.inorderwalk(): yield x
 yield self
 if self.right:
 for x in self.right.inorderwalk(): yield x
 def sillywalk(self):
 "Tiny, silly subset of `inorderwalk` functionality as requested."
 if self.left:
 self.left.sillywalk()
 print(self.payload)
 if self.right:
 self.right.sillywalk()

etc, etc -- basically like in any other language which uses references rather than pointers (such as Java, C#, etc).

Edit:

Of course, the very existence of sillywalk is silly indeed, because exactly the same functionality is a singe-liner external snippet on top of the walk method:

for x in tree.walk(): print(x.payload)

and with walk you can obtain just about any other functionality on the nodes-in-order stream, while, with sillywalk, you can obtain just about diddly-squat. But, hey, the OP says yield is "intimidating" (I wonder how many of Python 2.6's other 30 keywords deserve such scare words in the OP's judgment?-) so I'm hoping print isn't!

This is all completely beyond the actual question, on representing BSTs: that question is entirely answered in the __init__ -- a payload attribute to hold the node's payload, left and right attribute to hold either None (meaning, this node has no descendants on that side) or a Node (the top of the sub-tree of descendants on the appropriate side). Of course, the BST constraint is that every left descendant of each node (if any) has a payload less or equal than that of the node in question, every right one (again, if any) has a greater payload -- I added insert just to show how trivial it is to maintain that constraint, walk (and now sillywalk) to show how trivial it is to get all nodes in increasing order of payloads. Again, the general idea is just identical to the way you'd represent a BST in any language which uses references rather than pointers, like, for example, C# and Java.

• detly: You should space this out a bit, it's quite hard to read all together like that.
• Bunny Rabbit: @Alex Yield !!!! :| i am sure there's a less intimidating solution than this for a newbie like me.
• Alex Martelli: @Bunny, Python has very few keywords indeed (31, as of 2.6) -- which ones out of this tiny number do you find "intimidating"? Anyway, I'm going to add a completely silly and pointless walk-like method (working essentially just like walk but in an insanely restricted way) if that makes you happy (and add whitespace to make @detly happy too) -- editing the A accordingly.
• detly: @Bunny - don't be thinking yield is hard just because it's not common amongst other languages. Write maybe a couple of DIY examples and I'm sure it'll become much clearer.
• John Machin: @Alex: Any particular reason for using 0 instead of None in the __init__()?