How can I represent a binary tree in python?

Question

Currently I'm representing a binary tree in the following manner:

[None,2,[None,3,None]]

The tree above is rooted at 2. None means that the branch is empty.

I'd rather implement this in a list. Are there better ways to do this (without resorting to creating classes) ?

• Sven Marnach: Why the aribtrary limitation "without resorting to creating classes"? I think the best way to do this is to define a class.
• phynfo: "Better ways" in which respect? More efficient?
• bterwijn: Consider using a single flat list: stackoverflow.com/a/79560414/2429666

Answer 1

If you want to represent a complete binary tree (i.e. with all nodes having two children, except the leaves), then you can use just a flat list the represent the tree.

You can easily determine the father and two children of a node like this:

def leftChild(lst,i):
 try: 
 return lst[i*2]
 except IndexError:
 return None
def rightChild(lst,i):
 try: 
 return lst[i*2+1]
 except IndexError:
 return None
def father(lst,i):
 try:
 return lst[i/2]
 except IndexError:
 return None

Answer 2

It is possible to represent a binary tree using a flat list, as described here. How wasteful this method is would depend on the shape of your tree.

I am curious as to why you insist on avoiding classes. If you were to wrap this in a class, you could define a clean API and hide the details of your implementation from the eventual user.

Answer 3

Here is my way: an array of arrays, where item with index 0 is a root item:

[['Level A', 'A1', 'A2'], ['Level B', 'B1', 'B2'], ['Level C', 'C1', 'C2']]

Classes can make a simple application unnecessarily complex, especially if you deal with simple trees like represented above.