how to construct a binary-tree using python?

Carl J. Van Arsdall cvanarsdall at
Sat May 6 03:50:45 CEST 2006

hankssong wrote:
> Hi everyone, I'm wondering whether it's possible to construct a
> binary-tree using python.
> Since python don't have pointer, it can't dynamically allocate memory
> like C language.
> But some important data structures like linked list, binary-tree and
> hash table are closely linked with dynamic memory technology.
Its actually very possible to construct a binary tree in python.  If you 
do some googles searches you'll, in fact find, some implementations.

Its important to remember that python can dynamically make objects on 
the fly.  Objects are created as references and so you can make tree 
nodes whenever you want to

Here are some snippets, I'm not the most advanced coder but its just to 
show you that it can be done.

I wouldn't use this code verbatim, its taylored to a project I was doing 
at the time, but I hope this helps you get an idea.

class TreeNode:
  def __init__(self, nodeData):
    self.left = None
    self.right = None
[snip - stuff for my project]

class Tree:

  def __init__(self):
    self.root = None

  #assigns the data to a new TreeNode
  def addNode(self, inputData):
    return TreeNode(inputData)  #insert is recursive, so when it reaches 
its ending point this is called

  #this function traverses the tree and finds the spot to add the node
  def insertNode(self, inputData, root):
  def insertNode(self, inputData, root):
      if inputData.buildTag <= root.bTag:
        if root.left == None:
          root.left = self.addNode(inputData) #left is empty? add
          self.insertNode(inputData, root.left) #visit the left subtree
        if root.right == None:
          root.right = self.addNode(inputData)
          self.insertNode(inputData, root.right)
      return #root

  def findNode(self, nodeToFind, root): #nodeToFind is just a buildTag 
    if root == None:
      return None
     #btag is something i needed for what I was doing, ignore it
      #print "Comparing " + nodeToFind + " and " + root.bTag
      if nodeToFind == root.bTag:
        return root
      elif nodeToFind < root.bTag:
        return( self.findNode(nodeToFind, root.left) )
        return( self.findNode(nodeToFind, root.right) )


Carl J. Van Arsdall
cvanarsdall at
Build and Release
MontaVista Software

More information about the Python-list mailing list