How can I implement a tree in Python? Are there any built in data structures in Python like in Java?



I am trying to construct a general tree. Are there any built in data structures in Python to implement a tree?


Posted 2010-03-01T18:24:27.257

Reputation: 876

5 great explanation .... . – GrvTyagi – 2016-01-23T09:46:52.217




I recommend (I am the author)


from anytree import Node, RenderTree

udo = Node("Udo")
marc = Node("Marc", parent=udo)
lian = Node("Lian", parent=marc)
dan = Node("Dan", parent=udo)
jet = Node("Jet", parent=dan)
jan = Node("Jan", parent=dan)
joe = Node("Joe", parent=dan)


for pre, fill, node in RenderTree(udo):
    print("%s%s" % (pre,
├── Marc
│   └── Lian
└── Dan
    ├── Jet
    ├── Jan
    └── Joe

(Node('/Udo/Dan/Jet'), Node('/Udo/Dan/Jan'), Node('/Udo/Dan/Joe'))


anytree has also a powerful API with:

  • simple tree creation
  • simple tree modification
  • pre-order tree iteration
  • post-order tree iteration
  • resolve relative and absolute node paths
  • walking from one node to an other.
  • tree rendering (see example above)
  • node attach/detach hookups


Posted 2010-03-01T18:24:27.257

Reputation: 1 071


Python doesn't have the quite the extensive range of "built-in" data structures as Java does. However, because Python is dynamic, a general tree is easy to create. For example, a binary tree might be:

class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None = None

You can use it like this:

root = Tree() = "root"
root.left = Tree() = "left"
root.right = Tree() = "right"

Greg Hewgill

Posted 2010-03-01T18:24:27.257

Reputation: 657 778

11The question is tagged with Python3, there's no need to derive class Tree from object then – cfi – 2012-04-26T16:32:10.687


@cfi Deriving from object is sometimes just a guideline: If a class inherits from no other base classes, explicitly inherit from object. This also applies to nested classes. See Google Python Style Guide

– Konrad Reiche – 2012-09-27T09:39:20.413

13@platzhirsch: Please read and quote the guideline completely: Google explicitly points out that this is required for Python 2 code to work as expected and recommended to improve compatibility with Py3. Here we're talking about Py3 code. There's no need to do extra, legacy typing. – cfi – 2012-09-27T10:45:29.030

1@cfi I totally read over this, thanks for pointing out. – Konrad Reiche – 2012-09-27T11:29:39.170

82This doesn't really explain much about making a useful tree implementation. – Mike Graham – 2010-03-01T19:54:33.197

5That's a binary tree, not a general one as asked for. – Michael Dorner – 2016-10-27T08:12:08.953

@Greg Hewgill Are you able to provide an example where the "binary" is generic, e.g. the size of splits per node is unknown? In form of a List. – Jan Hackenberg – 2017-11-19T00:29:47.600

@JanHackenberg I have used this simple one in the past:

– Wok – 2018-05-22T07:36:53.533


A generic tree is a node with zero or more children, each one a proper (tree) node. It isn't the same as a binary tree, they're different data structures, although both shares some terminology.

There isn't any builtin data structure for generic trees in Python, but it's easily implemented with classes.

class Tree(object):
    "Generic tree node."
    def __init__(self, name='root', children=None): = name
        self.children = []
        if children is not None:
            for child in children:
    def __repr__(self):
    def add_child(self, node):
        assert isinstance(node, Tree)
#    *
#   /|\
#  1 2 +
#     / \
#    3   4
t = Tree('*', [Tree('1'),
               Tree('+', [Tree('3'),


Posted 2010-03-01T18:24:27.257

Reputation: 802

Amazing, this can be easily used as a graph too! The only problem that i saw is: How can I differ the left node from the right node? – Ângelo Polotto – 2018-10-30T20:48:46.523


You can try:

from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'

As suggested here:


Posted 2010-03-01T18:24:27.257

Reputation: 2 771

if you want to extend to an an arbitrary amount of levels check:

– natbusa – 2017-04-05T16:56:18.397

this shadows the built in function hash. – Tritium21 – 2017-06-01T07:27:09.833


There aren't trees built in, but you can easily construct one by subclassing a Node type from List and writing the traversal methods. If you do this, I've found bisect useful.

There are also many implementations on PyPi that you can browse.

If I remember correctly, the Python standard lib doesn't include tree data structures for the same reason that the .NET base class library doesn't: locality of memory is reduced, resulting in more cache misses. On modern processors it's usually faster to just bring a large chunk of memory into the cache, and "pointer rich" data structures negate the benefit.

Justin R.

Posted 2010-03-01T18:24:27.257

Reputation: 15 706

2FYI: The interwebs are plastered with hatred against Boost. Apparently it's supposed to be a HUGE pain to deal with, especially since support for it has been discontinued. So I would recommend staying away from that – inspectorG4dget – 2010-03-01T18:54:04.770

Thanks. I haven't had any trouble personally, but I don't want to mislead so I've removed that reference. – Justin R. – 2010-03-01T18:58:04.263


class Node:
    Class Node
    def __init__(self, value):
        self.left = None = value
        self.right = None

class Tree:
    Class tree will provide a tree as well as utility functions.

    def createNode(self, data):
        Utility function to create a node.
        return Node(data)

    def insert(self, node , data):
        Insert function will insert a node into tree.
        Duplicate keys are not allowed.
        #if tree is empty , return a root node
        if node is None:
            return self.createNode(data)
        # if data is smaller than parent , insert it into left side
        if data <
            node.left = self.insert(node.left, data)
        elif data >
            node.right = self.insert(node.right, data)

        return node

    def search(self, node, data):
        Search function will search a node into tree.
        # if root is None or root is the search data.
        if node is None or == data:
            return node

        if < data:
            return, data)
            return, data)

    def deleteNode(self,node,data):
        Delete function will delete a node into tree.
        Not complete , may need some more scenarion that we can handle
        Now it is handling only leaf.

        # Check if tree is empty.
        if node is None:
            return None

        # searching key into BST.
        if data <
            node.left = self.deleteNode(node.left, data)
        elif data >
            node.right = self.deleteNode(node.right, data)
        else: # reach to the node that need to delete from BST.
            if node.left is None and node.right is None:
                del node
            if node.left == None:
                temp = node.right
                del node
                return  temp
            elif node.right == None:
                temp = node.left
                del node
                return temp

        return node

    def traverseInorder(self, root):
        traverse function will print all the node in the tree.
        if root is not None:

    def traversePreorder(self, root):
        traverse function will print all the node in the tree.
        if root is not None:

    def traversePostorder(self, root):
        traverse function will print all the node in the tree.
        if root is not None:

def main():
    root = None
    tree = Tree()
    root = tree.insert(root, 10)
    print root
    tree.insert(root, 20)
    tree.insert(root, 30)
    tree.insert(root, 40)
    tree.insert(root, 70)
    tree.insert(root, 60)
    tree.insert(root, 80)

    print "Traverse Inorder"

    print "Traverse Preorder"

    print "Traverse Postorder"

if __name__ == "__main__":

shivam garg

Posted 2010-03-01T18:24:27.257

Reputation: 161

3Can you add just some notes to introduce your code and your implementation? – Michele d'Amico – 2015-04-09T07:34:34.527


I implemented a rooted tree as a dictionary {child:parent}. So for instance with the root node 0, a tree might look like that:

tree={1:0, 2:0, 3:1, 4:2, 5:3}

This structure made it quite easy to go upward along a path from any node to the root, which was relevant for the problem I was working on.


Posted 2010-03-01T18:24:27.257

Reputation: 91

1This is the way I was considering doing it, until I saw the answer. Although since a tree is a parent with two children, and if you want to go down, you can do {parent:[leftchild,rightchild]}. – JFA – 2014-03-20T00:37:59.187

1Another way is to use lists of lists where the first (or more) element in the list is the node value, and the following nested two lists represent its left and right subtrees (or more for n-ary tree). – pepr – 2014-05-04T10:14:15.937


Greg Hewgill's answer is great but if you need more nodes per level you can use a list|dictionary to create them: And then use method to access them either by name or order (like id)

class node(object):
    def __init__(self):
        self.otherInfo = None
    def nex(self,child):
        "Gets a node by number"
        return self.node[child]
    def prev(self):
        return self.prev
    def goto(self,data):
        "Gets the node by name"
        for child in range(0,len(self.node)):
                return self.node[child]
    def add(self):
        return node1

Now just create a root and build it up: ex:

tree=node()  #create a node"root" #name it root
tree.otherInfo="blue" #or what ever 
tree=tree.add() #add a node to the root"node1" #name it





        /    \
grandchild1 gchild2


             /   \
        child1  child2
       /     \
grandchild1 gchild2

tree=tree.goto("child1") or tree=tree.nex(0)"changed"

              /   \
         changed   child2
        /      \
  grandchild1  gchild2

That should be enough for you to start figuring out how to make this work


Posted 2010-03-01T18:24:27.257

Reputation: 172

There's something is missing in this answer, I was trying this solution for the past 2 days and I think you have some logical flow in the object addition method. I will submit my answer to this question, please check that out and let me know if I can help. – MAULIK MODI – 2018-10-14T03:37:50.107


class Tree(dict):
    """A tree implementation using python's autovivification feature."""
    def __missing__(self, key):
        value = self[key] = type(self)()
        return value

    #cast a (nested) dict to a (nested) Tree class
    def __init__(self, data={}):
        for k, data in data.items():
            if isinstance(data, dict):
                self[k] = type(self)(data)
                self[k] = data

works as a dictionary, but provides as many nested dicts you want. Try the following:

your_tree = Tree()

your_tree['a']['1']['x']  = '@'
your_tree['a']['1']['y']  = '#'
your_tree['a']['2']['x']  = '$'
your_tree['a']['3']       = '%'
your_tree['b']            = '*'

will deliver a nested dict ... which works as a tree indeed.

{'a': {'1': {'x': '@', 'y': '#'}, '2': {'x': '$'}, '3': '%'}, 'b': '*'}

... If you have already a dict, it will cast each level to a tree:

d = {'foo': {'amy': {'what': 'runs'} } }
tree = Tree(d)

print(d['foo']['amy']['what']) # returns 'runs'
d['foo']['amy']['when'] = 'now' # add new branch

In this way, you can keep edit/add/remove each dict level as you wish. All the dict methods for traversal etc, still apply.


Posted 2010-03-01T18:24:27.257

Reputation: 914


I've implemented trees using nested dicts. It is quite easy to do, and it has worked for me with pretty large data sets. I've posted a sample below, and you can see more at Google code

  def addBallotToTree(self, tree, ballotIndex, ballot=""):
    """Add one ballot to the tree.

    The root of the tree is a dictionary that has as keys the indicies of all 
    continuing and winning candidates.  For each candidate, the value is also
    a dictionary, and the keys of that dictionary include "n" and "bi".
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.

    If candidate c is a winning candidate, then that portion of the tree is
    expanded to indicate the breakdown of the subsequently ranked candidates.
    In this situation, additional keys are added to the tree[c] dictionary
    corresponding to subsequently ranked candidates.
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
    tree[c][d]["n"] is the number of ballots that rank c first and d second.
    tree[c][d]["bi"] is a list of the corresponding ballot indices.

    Where the second ranked candidates is also a winner, then the tree is 
    expanded to the next level.  

    Losing candidates are ignored and treated as if they do not appear on the 
    ballots.  For example, tree[c][d]["n"] is the total number of ballots
    where candidate c is the first non-losing candidate, c is a winner, and
    d is the next non-losing candidate.  This will include the following
    ballots, where x represents a losing candidate:
    [c d]
    [x c d]
    [c x d]
    [x c x x d]

    During the count, the tree is dynamically updated as candidates change
    their status.  The parameter "tree" to this method may be the root of the
    tree or may be a sub-tree.

    if ballot == "":
      # Add the complete ballot to the tree
      weight, ballot = self.b.getWeightedBallot(ballotIndex)
      # When ballot is not "", we are adding a truncated ballot to the tree,
      # because a higher-ranked candidate is a winner.
      weight = self.b.getWeight(ballotIndex)

    # Get the top choice among candidates still in the running
    # Note that we can't use Ballots.getTopChoiceFromWeightedBallot since
    # we are looking for the top choice over a truncated ballot.
    for c in ballot:
      if c in self.continuing |
        break # c is the top choice so stop
      c = None # no candidates left on this ballot

    if c is None:
      # This will happen if the ballot contains only winning and losing
      # candidates.  The ballot index will not need to be transferred
      # again so it can be thrown away.

    # Create space if necessary.
    if not tree.has_key(c):
      tree[c] = {}
      tree[c]["n"] = 0
      tree[c]["bi"] = []

    tree[c]["n"] += weight

    if c in
      # Because candidate is a winner, a portion of the ballot goes to
      # the next candidate.  Pass on a truncated ballot so that the same
      # candidate doesn't get counted twice.
      i = ballot.index(c)
      ballot2 = ballot[i+1:]
      self.addBallotToTree(tree[c], ballotIndex, ballot2)
      # Candidate is in continuing so we stop here.

Jeff O'Neill

Posted 2010-03-01T18:24:27.257

Reputation: 8 048

3404 error on link – robert king – 2013-01-07T22:47:11.977


I've published a Python [3] tree implementation on my site:

Hope it is of use,

Ok, here's the code:

import uuid

def sanitize_id(id):
    return id.strip().replace(" ", "")

(_ADD, _DELETE, _INSERT) = range(3)
(_ROOT, _DEPTH, _WIDTH) = range(3)

class Node:

    def __init__(self, name, identifier=None, expanded=True):
        self.__identifier = (str(uuid.uuid1()) if identifier is None else
                sanitize_id(str(identifier))) = name
        self.expanded = expanded
        self.__bpointer = None
        self.__fpointer = []

    def identifier(self):
        return self.__identifier

    def bpointer(self):
        return self.__bpointer

    def bpointer(self, value):
        if value is not None:
            self.__bpointer = sanitize_id(value)

    def fpointer(self):
        return self.__fpointer

    def update_fpointer(self, identifier, mode=_ADD):
        if mode is _ADD:
        elif mode is _DELETE:
        elif mode is _INSERT:
            self.__fpointer = [sanitize_id(identifier)]

class Tree:

    def __init__(self):
        self.nodes = []

    def get_index(self, position):
        for index, node in enumerate(self.nodes):
            if node.identifier == position:
        return index

    def create_node(self, name, identifier=None, parent=None):

        node = Node(name, identifier)
        self.__update_fpointer(parent, node.identifier, _ADD)
        node.bpointer = parent
        return node

    def show(self, position, level=_ROOT):
        queue = self[position].fpointer
        if level == _ROOT:
            print("{0} [{1}]".format(self[position].name,
            print("\t"*level, "{0} [{1}]".format(self[position].name,
        if self[position].expanded:
            level += 1
            for element in queue:
      , level)  # recursive call

    def expand_tree(self, position, mode=_DEPTH):
        # Python generator. Loosly based on an algorithm from 'Essential LISP' by
        # John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241
        yield position
        queue = self[position].fpointer
        while queue:
            yield queue[0]
            expansion = self[queue[0]].fpointer
            if mode is _DEPTH:
                queue = expansion + queue[1:]  # depth-first
            elif mode is _WIDTH:
                queue = queue[1:] + expansion  # width-first

    def is_branch(self, position):
        return self[position].fpointer

    def __update_fpointer(self, position, identifier, mode):
        if position is None:
            self[position].update_fpointer(identifier, mode)

    def __update_bpointer(self, position, identifier):
        self[position].bpointer = identifier

    def __getitem__(self, key):
        return self.nodes[self.get_index(key)]

    def __setitem__(self, key, item):
        self.nodes[self.get_index(key)] = item

    def __len__(self):
        return len(self.nodes)

    def __contains__(self, identifier):
        return [node.identifier for node in self.nodes
                if node.identifier is identifier]

if __name__ == "__main__":

    tree = Tree()
    tree.create_node("Harry", "harry")  # root node
    tree.create_node("Jane", "jane", parent = "harry")
    tree.create_node("Bill", "bill", parent = "harry")
    tree.create_node("Joe", "joe", parent = "jane")
    tree.create_node("Diane", "diane", parent = "jane")
    tree.create_node("George", "george", parent = "diane")
    tree.create_node("Mary", "mary", parent = "diane")
    tree.create_node("Jill", "jill", parent = "george")
    tree.create_node("Carol", "carol", parent = "jill")
    tree.create_node("Grace", "grace", parent = "bill")
    tree.create_node("Mark", "mark", parent = "jane")

    for node in tree.expand_tree("harry", mode=_WIDTH):

Brett Kromkamp

Posted 2010-03-01T18:24:27.257

Reputation: 179


What operations do you need? There is often a good solution in Python using a dict or a list with the bisect module.

There are many, many tree implementations on PyPI, and many tree types are nearly trivial to implement yourself in pure Python. However, this is rarely necessary.

Mike Graham

Posted 2010-03-01T18:24:27.257

Reputation: 49 204


Another tree implementation loosely based off of Bruno's answer:

class Node:
    def __init__(self): str = ''
        self.children: List[Node] = []
        self.parent: Node = self

    def __getitem__(self, i: int) -> 'Node':
        return self.children[i]

    def add_child(self):
        child = Node()
        child.parent = self
        return child

    def __str__(self) -> str:
        def _get_character(x, left, right) -> str:
            if x < left:
                return '/'
            elif x >= right:
                return '\\'
                return '|'

        if len(self.children):
            children_lines: Sequence[List[str]] = list(map(lambda child: str(child).split('\n'), self.children))
            widths: Sequence[int] = list(map(lambda child_lines: len(child_lines[0]), children_lines))
            max_height: int = max(map(len, children_lines))
            total_width: int = sum(widths) + len(widths) - 1
            left: int = (total_width - len( + 1) // 2
            right: int = left + len(

            return '\n'.join((
                ' '.join(map(lambda width, position: _get_character(position - width // 2, left, right).center(width),
                             widths, accumulate(widths, add))),
                    lambda row: ' '.join(map(
                        lambda child_lines: child_lines[row] if row < len(child_lines) else ' ' * len(child_lines[0]),

And an example of how to use it:

tree = Node() = 'Root node'
tree[0].name = 'Child node 0'
tree[1].name = 'Child node 1'
tree[2].name = 'Child node 2'
tree[1][0].name = 'Grandchild 1.0'
tree[2][0].name = 'Grandchild 2.0'
tree[2][1].name = 'Grandchild 2.1'

Which should output:

                        Root node                        
     /             /                      \              
Child node 0  Child node 1           Child node 2        
                   |              /              \       
             Grandchild 1.0 Grandchild 2.0 Grandchild 2.1

Solomon Ucko

Posted 2010-03-01T18:24:27.257

Reputation: 600


If you want to create a tree data structure then first you have to create the treeElement object. If you create the treeElement object, then you can decide how your tree behaves.

To do this following is the TreeElement class:

class TreeElement (object):

def __init__(self):
    self.elementName = None
    self.element = []
    self.previous = None
    self.elementScore = None
    self.elementParent = None
    self.elementPath = []
    self.treeLevel = 0

def goto(self, data):
    for child in range(0, len(self.element)):
        if (self.element[child].elementName == data):
            return self.element[child]

def add(self):

    single_element = TreeElement()
    single_element.elementName = self.elementName
    single_element.previous = self.elementParent
    single_element.elementScore = self.elementScore
    single_element.elementPath = self.elementPath
    single_element.treeLevel = self.treeLevel


    return single_element

Now, we have to use this element to create the tree, I am using A* tree in this example.

class AStarAgent(Agent):
# Initialization Function: Called one time when the game starts
def registerInitialState(self, state):

# GetAction Function: Called with every frame
def getAction(self, state):

    # Sorting function for the queue
    def sortByHeuristic(each_element):

        if each_element.elementScore:
            individual_score = each_element.elementScore[0][0] + each_element.treeLevel
            individual_score = admissibleHeuristic(each_element)

        return individual_score

    # check the game is over or not
    if state.isWin():
        print('Job is done')
        return Directions.STOP
    elif state.isLose():
        print('you lost')
        return Directions.STOP

    # Create empty list for the next states
    astar_queue = []
    astar_leaf_queue = []
    astar_tree_level = 0
    parent_tree_level = 0

    # Create Tree from the give node element
    astar_tree = TreeElement()
    astar_tree.elementName = state
    astar_tree.treeLevel = astar_tree_level
    astar_tree = astar_tree.add()

    # Add first element into the queue

    # Traverse all the elements of the queue
    while astar_queue:

        # Sort the element from the queue
        if len(astar_queue) > 1:
            astar_queue.sort(key=lambda x: sortByHeuristic(x))

        # Get the first node from the queue
        astar_child_object = astar_queue.pop(0)
        astar_child_state = astar_child_object.elementName

        # get all legal actions for the current node
        current_actions = astar_child_state.getLegalPacmanActions()

        if current_actions:

            # get all the successor state for these actions
            for action in current_actions:

                # Get the successor of the current node
                next_state = astar_child_state.generatePacmanSuccessor(action)

                if next_state:

                    # evaluate the successor states using scoreEvaluation heuristic
                    element_scored = [(admissibleHeuristic(next_state), action)]

                    # Increase the level for the child
                    parent_tree_level = astar_tree.goto(astar_child_state)
                    if parent_tree_level:
                        astar_tree_level = parent_tree_level.treeLevel + 1
                        astar_tree_level += 1

                    # create tree for the finding the data
                    astar_tree.elementName = next_state
                    astar_tree.elementParent = astar_child_state
                    astar_tree.elementScore = element_scored
                    astar_tree.treeLevel = astar_tree_level
                    astar_object = astar_tree.add()

                    # If the state exists then add that to the queue

                    # Update the value leaf into the queue
                    astar_leaf_state = astar_tree.goto(astar_child_state)

You can add/remove any elements from the object, but make the structure intect.


Posted 2010-03-01T18:24:27.257

Reputation: 77


def iterative_bfs(graph, start):
    '''iterative breadth first search from start'''
    bfs_tree = {start: {"parents":[], "children":[], "level":0}}
    q = [start]
    while q:
        current = q.pop(0)
        for v in graph[current]:
            if not v in bfs_tree:
                bfs_tree[v]={"parents":[current], "children":[], "level": bfs_tree[current]["level"] + 1}
                if bfs_tree[v]["level"] > bfs_tree[current]["level"]:

Gagan Nirmal

Posted 2010-03-01T18:24:27.257

Reputation: 1