How to implement a binary tree?

Question

Which is the best data structure that can be used to implement a binary tree in Python?

Solution 1

Here is my simple recursive implementation of binary search tree.

#!/usr/bin/python

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

class Tree:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self, val):
        if self.root is None:
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if val < node.v:
            if node.l is not None:
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if node.r is not None:
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val):
        if self.root is not None:
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if val == node.v:
            return node
        elif (val < node.v and node.l is not None):
            return self._find(val, node.l)
        elif (val > node.v and node.r is not None):
            return self._find(val, node.r)

    def deleteTree(self):
        # garbage collector will do this for us. 
        self.root = None

    def printTree(self):
        if self.root is not None:
            self._printTree(self.root)

    def _printTree(self, node):
        if node is not None:
            self._printTree(node.l)
            print(str(node.v) + ' ')
            self._printTree(node.r)

#     3
# 0     4
#   2      8
tree = Tree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.printTree()
print(tree.find(3).v)
print(tree.find(10))
tree.deleteTree()
tree.printTree()

Solution 2

[What you need for interviews] A Node class is the sufficient data structure to represent a binary tree.

(While other answers are mostly correct, they are not required for a binary tree: no need to extend object class, no need to be a BST, no need to import deque).

class Node:

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

Here is an example of a tree:

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n1.left  = n2
n1.right = n3

In this example n1 is the root of the tree having n2, n3 as its children.

Solution 3

# simple binary tree
# in this implementation, a node is inserted between an existing node and the root


class BinaryTree():

    def __init__(self,rootid):
      self.left = None
      self.right = None
      self.rootid = rootid

    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right
    def setNodeValue(self,value):
        self.rootid = value
    def getNodeValue(self):
        return self.rootid

    def insertRight(self,newNode):
        if self.right == None:
            self.right = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            tree.right = self.right
            self.right = tree
        
    def insertLeft(self,newNode):
        if self.left == None:
            self.left = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            tree.left = self.left
            self.left = tree


def printTree(tree):
        if tree != None:
            printTree(tree.getLeftChild())
            print(tree.getNodeValue())
            printTree(tree.getRightChild())
            


# test tree

def testTree():
    myTree = BinaryTree("Maud")
    myTree.insertLeft("Bob")
    myTree.insertRight("Tony")
    myTree.insertRight("Steven")
    printTree(myTree)
        

Read more about it Here:-This is a very simple implementation of a binary tree.

This is a nice tutorial with questions in between

Solution 4

Simple implementation of BST in Python

class TreeNode:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.data = value

class Tree:
    def __init__(self):
        self.root = None

    def addNode(self, node, value):
        if(node==None):
            self.root = TreeNode(value)
        else:
            if(value<node.data):
                if(node.left==None):
                    node.left = TreeNode(value)
                else:
                    self.addNode(node.left, value)
            else:
                if(node.right==None):
                    node.right = TreeNode(value)
                else:
                    self.addNode(node.right, value)

    def printInorder(self, node):
        if(node!=None):
            self.printInorder(node.left)
            print(node.data)
            self.printInorder(node.right)

def main():
    testTree = Tree()
    testTree.addNode(testTree.root, 200)
    testTree.addNode(testTree.root, 300)
    testTree.addNode(testTree.root, 100)
    testTree.addNode(testTree.root, 30)
    testTree.printInorder(testTree.root)

Solution 5

A very quick 'n dirty way of implementing a binary tree using lists. Not the most efficient, nor does it handle nil values all too well. But it's very transparent (at least to me):

def _add(node, v):
    new = [v, [], []]
    if node:
        left, right = node[1:]
        if not left:
            left.extend(new)
        elif not right:
            right.extend(new)
        else:
            _add(left, v)
    else:
        node.extend(new)

def binary_tree(s):
    root = []
    for e in s:
        _add(root, e)
    return root

def traverse(n, order):
    if n:
        v = n[0]
        if order == 'pre':
            yield v
        for left in traverse(n[1], order):
            yield left
        if order == 'in':
            yield v
        for right in traverse(n[2], order):
            yield right
        if order == 'post':
            yield v

Constructing a tree from an iterable:

 >>> tree = binary_tree('A B C D E'.split())
 >>> print tree
 ['A', ['B', ['D', [], []], ['E', [], []]], ['C', [], []]]

Traversing a tree:

 >>> list(traverse(tree, 'pre')), list(traverse(tree, 'in')), list(traverse(tree, 'post'))
 (['A', 'B', 'D', 'E', 'C'],
  ['D', 'B', 'E', 'A', 'C'],
  ['D', 'E', 'B', 'C', 'A'])

View more solutions

Comments

[water0]

After running this, the new nodes z, y, x, w, u, v sometimes could be assign, sometimes would has bugs, like this: print u.key AttributeError: 'NoneType' object has no attribute 'key' I wonder how to fix it up, thanks

[talonmies]

The code in insertLeft is broken and will produce an infinite loop on any attempt to recursively traverse down the leftmost branch the binary tree

[Jeff Mandell]

Nice implementation. I'm just here to point out some style stuff. python usually does node is not None instead of your (node!=None). Also, you can use the __str__ function instead of the printTree method.

[darkhipo]

Also, your _find should probably be: def _find(self, val, node): if(val == node.v): return node elif(val < node.v and node.l != None): return self._find(val, node.l) elif(val > node.v and node.r != None): return self._find(val, node.r)

[Sagar Shah]

Isnt this a binary search tree whereleft<=root<=right ?

[djra]

@SagarShah yes it's binary search tree. And from _printTree function tree traversal is, as you said, L R R.

[Jagoda]

It can be easily fixed by swaping the following lines: tree.left = self.left self.left = tree

[Admin]

It is better to have two classes. That is better implementation

[Tony Wang]

tree.find(0) ,tree.find(2) ,tree.find(4),tree.find(8) all return None.

[Maorg]

To further ellaborate @TonyWang's comment, you should change the _find() method such that it will return the recursive calls to the function. In the way you wrote it, the value goes back to the calling function without passing the value back. Now works: def _find(self, node, val): if val == node.value: return node elif val > node.value and node.right is not None: return self._find(node.right, val) elif val < node.value and node.left is not None: return self._find(node.left, val) else: return None

[Guy]

@user3022012 your comment is simply wrong. by definition, a tree is composed of data, and sub trees (for binary tree, it's two sub-trees), which are also trees. No reason, whatsoever to tree the root node differently.

[Guy]

the original poster only asked for a binary tree implementation and not a binary search tree...

[Diego Gallegos]

There is a small bug, when you try to insert an existing key then it goes down the tree to create a new node with the a duplicate key.

[thayne]

Very nice! I couldn't help but comment that the resulting tree does not hold the invariant that all elements in the left subtree are less than v. - A property that is important for binary search trees. (Yes I realize that OP did not ask for a "search tree") however, FWIW it can be done with a simple modification to the check in _add(). Then your inorder traversal gives a sorted list.

[Arjee]

the last link is broken. Can you fix it.

[Svante]

The pre-order traversal is wrong: you need to test each branch separately.

[shanks]

I think, you need to test each branch separately only in case of in order and post order. pre-order method I wrote , gives right result. Can you tell me in which case this method will break? However, let me test both branches separately as I have done for post-order and in-order

[Svante]

The way it was, if the left child was None, it wouldn't even look at the right child.

[outlier229]

You have ended some sentences with a semicolon and some without a semicolon. Could you please explain the reason for that? P.S - I am a Python beginner, that's why asking such a basic question.

[eshanrh]

I mean, if a binary tree's left child is none, we can assume that the right child is none as well. If a node branches into 2 and only 2 nodes, and the left one is None, the right one will also be None.

[physicsGuy]

@outlier229 All the semicolons in the code above are optional, removing them doesn't change anything. My guess is that Fox is simply used to coding a language like C++ or Java, which require the semicolon at the end of the line. Aside from that optional use, semicolons can be used to chain statements in a single line. For example a=1; b=2; c=3 would be a valid single line in python.

[apadana]

@Sneftel Other answers are over sophisticated for a binary tree. This is the required piece which is needed for a binary tree implementation. Other answers are making it too difficult for new people to understand so I thought just post the bare minimum to help newer people. Some of the other answers are good for articles and journal papers ;) This is also the piece that someone needs for software interviews.

[fbparis]

I prefer non recursive implementations but at least you should make the Node class a child of "object" and declare a slots = "l","v","r" in the class definition. As you may have a lot of nodes, it could save a good amount of memory...

[Scrubster]

This isn't a binary tree. It is a binary search tree.

[pylang]

It adds simplicity, which is valuable.

[Apostolos]

Simple and very logical. Great. I loved it!

[kd4ttc]

Adding the diagram was brilliant!

[mherzog]

This is a Binary Search Tree, which is a subset of a Binary Tree, where the left node is less than the right.