Which is the best data structure that can be used to implement a binary tree in Python?
How to implement a binary tree?
Asked Answered
Lot of solutions here are implementing BST but questionsasked Biner Tree Implementation –
Cruickshank
Maybe specify that you want the tree algorithm in Python in the title of the question? –
Recurrent
Here is my simple recursive implementation of binary search tree.
#!/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 get_root(self):
return self.root
def add(self, val):
if not self.root:
self.root = Node(val)
else:
self._add(val, self.root)
def _add(self, val, node):
if val < node.v:
if node.l:
self._add(val, node.l)
else:
node.l = Node(val)
else:
if node.r:
self._add(val, node.r)
else:
node.r = Node(val)
def find(self, val):
if self.root:
return self._find(val, self.root)
def _find(self, val, node):
if val == node.v:
return node
elif val < node.v and node.l:
return self._find(val, node.l)
elif val > node.v and node.r:
return self._find(val, node.r)
def delete_tree(self):
# garbage collector will do this for us.
if self.root:
self.root = None
def view_tree(self):
if self.root:
self._view_tree(self.root)
def _view_tree(self, node):
if node:
self._view_tree(node.l)
print(node.v, end = " ")
self._view_tree(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.view_tree()
print(tree.find(3).v)
print(tree.find(10))
tree.delete_tree()
tree.view_tree()
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. –
Muchness 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) –
Gerfen Isnt this a binary search tree where
left<=root<=right ? –
Domesday @SagarShah yes it's binary search tree. And from _printTree function tree traversal is, as you said, L R R. –
Charbonnier
tree.find(0) ,tree.find(2) ,tree.find(4),tree.find(8) all return None. –
Pace
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 –
Spinode
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. –
Kessel
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... –
Ecclesia
This isn't a binary tree. It is a binary search tree. –
Chanellechaney
[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.
@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. –
Adelaideadelaja
It adds simplicity, which is valuable. –
Squeaky
Simple and very logical. Great. I loved it! –
Overexert
Adding the diagram was brilliant! –
Orella
# 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
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 –
Poss It can be easily fixed by swaping the following lines: tree.left = self.left self.left = tree –
Poon
the last link is broken. Can you fix it. –
Centriole
I can't help but notice that most answers here are implementing a Binary Search Tree. Binary Search Tree != Binary Tree.
A Binary Search Tree has a very specific property: for any node X, X's key is larger than the key of any descendent of its left child, and smaller than the key of any descendant of its right child.
A Binary Tree imposes no such restriction. A Binary Tree is simply a data structure with a 'key' element, and two children, say 'left' and 'right'.
A Tree is an even more general case of a Binary Tree where each node can have an arbitrary number of children. Typically, each node has a 'children' element which is of type list/array.
Now, to answer the OP's question, I am including a full implementation of a Binary Tree in Python. The underlying data structure storing each BinaryTreeNode is a dictionary, given it offers optimal O(1) lookups. I've also implemented depth-first and breadth-first traversals. These are very common operations performed on trees.
from collections import deque
class BinaryTreeNode:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def __repr__(self):
return "%s l: (%s) r: (%s)" % (self.key, self.left, self.right)
def __eq__(self, other):
if self.key == other.key and \
self.right == other.right and \
self.left == other.left:
return True
else:
return False
class BinaryTree:
def __init__(self, root_key=None):
# maps from BinaryTreeNode key to BinaryTreeNode instance.
# Thus, BinaryTreeNode keys must be unique.
self.nodes = {}
if root_key is not None:
# create a root BinaryTreeNode
self.root = BinaryTreeNode(root_key)
self.nodes[root_key] = self.root
def add(self, key, left_key=None, right_key=None):
if key not in self.nodes:
# BinaryTreeNode with given key does not exist, create it
self.nodes[key] = BinaryTreeNode(key)
# invariant: self.nodes[key] exists
# handle left child
if left_key is None:
self.nodes[key].left = None
else:
if left_key not in self.nodes:
self.nodes[left_key] = BinaryTreeNode(left_key)
# invariant: self.nodes[left_key] exists
self.nodes[key].left = self.nodes[left_key]
# handle right child
if right_key == None:
self.nodes[key].right = None
else:
if right_key not in self.nodes:
self.nodes[right_key] = BinaryTreeNode(right_key)
# invariant: self.nodes[right_key] exists
self.nodes[key].right = self.nodes[right_key]
def remove(self, key):
if key not in self.nodes:
raise ValueError('%s not in tree' % key)
# remove key from the list of nodes
del self.nodes[key]
# if node removed is left/right child, update parent node
for k in self.nodes:
if self.nodes[k].left and self.nodes[k].left.key == key:
self.nodes[k].left = None
if self.nodes[k].right and self.nodes[k].right.key == key:
self.nodes[k].right = None
return True
def _height(self, node):
if node is None:
return 0
else:
return 1 + max(self._height(node.left), self._height(node.right))
def height(self):
return self._height(self.root)
def size(self):
return len(self.nodes)
def __repr__(self):
return str(self.traverse_inorder(self.root))
def bfs(self, node):
if not node or node not in self.nodes:
return
reachable = []
q = deque()
# add starting node to queue
q.append(node)
while len(q):
visit = q.popleft()
# add currently visited BinaryTreeNode to list
reachable.append(visit)
# add left/right children as needed
if visit.left:
q.append(visit.left)
if visit.right:
q.append(visit.right)
return reachable
# visit left child, root, then right child
def traverse_inorder(self, node, reachable=None):
if not node or node.key not in self.nodes:
return
if reachable is None:
reachable = []
self.traverse_inorder(node.left, reachable)
reachable.append(node.key)
self.traverse_inorder(node.right, reachable)
return reachable
# visit left and right children, then root
# root of tree is always last to be visited
def traverse_postorder(self, node, reachable=None):
if not node or node.key not in self.nodes:
return
if reachable is None:
reachable = []
self.traverse_postorder(node.left, reachable)
self.traverse_postorder(node.right, reachable)
reachable.append(node.key)
return reachable
# visit root, left, then right children
# root is always visited first
def traverse_preorder(self, node, reachable=None):
if not node or node.key not in self.nodes:
return
if reachable is None:
reachable = []
reachable.append(node.key)
self.traverse_preorder(node.left, reachable)
self.traverse_preorder(node.right, reachable)
return reachable
True about not every binary tree is a search tree. Consequently, don't call the node data key. –
Turntable
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)
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. –
Mozart
@Mozart 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. –
Arrowood
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'])
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. –
Chewning
A Node-based class of connected nodes is a standard approach. These can be hard to visualize.
Motivated from an essay on Python Patterns - Implementing Graphs, consider a simple dictionary:
Given
A binary tree
a
/ \
b c
/ \ \
d e f
Code
Make a dictionary of unique nodes:
tree = {
"a": ["b", "c"],
"b": ["d", "e"],
"c": [None, "f"],
"d": [None, None],
"e": [None, None],
"f": [None, None],
}
Details
- Each key-value pair is a unique node pointing to its children.
- A list (or tuple) holds an ordered pair of left/right children.
- With a dict having ordered insertion, assume the first entry is the root.
- Common methods can be functions that mutate or traverse the dict (see
find_all_paths()).
Tree-based functions often include the following common operations:
- traverse: yield each node in a given order (usually left-to-right)
- breadth-first search (BFS): traverse levels
- depth-first search (DFS): traverse branches first (pre-/in-/post-order)
- insert: add a node to the tree depending on the number of children
- remove: remove a node depending on the number of children
- update: merge missing nodes from one tree to the other
- visit: yield the value of a traversed node
Try implementing all of these operations. Here we demonstrate one of these functions - a BFS traversal:
Example
import collections as ct
def traverse(tree):
"""Yield nodes from a tree via BFS."""
q = ct.deque() # 1
root = next(iter(tree)) # 2
q.append(root)
while q:
node = q.popleft()
children = filter(None, tree.get(node))
for n in children: # 3
q.append(n)
yield node
list(traverse(tree))
# ['a', 'b', 'c', 'd', 'e', 'f']
This is a breadth-first search (level-order) algorithm applied to a dict of nodes and children.
- Initialize
dequeand later use the.popleft()method to emulate a FIFO queue. - Get and enqueue the root node (assumes the root is the first entry in the dict, Python 3.6+).
- Iterate and dequeue a node, enqueue its children and yield the node value.
See also this in-depth tutorial on trees.
Insight
We can easily switch between BFS and DFS traversal techniques through replacing the underlying data-structure. A reminder:
- breadth-first search (BFS): use a FIFO data-structure (a.k.a. "
queue"), e.g.queue.queue,collections.deque(as seen above) - depth-first search (DFS): use a LIFO data-structure (a.k.a. stack), e.g.
list,collections.deque
A FIFO (first in, first out) data-structure will add items on one end and exit the opposite end. A LIFO (last in, first out) data-structure will add items on the same side they exit.
A deque can emulate either FIFO or LIFO depending on which .pop*() method is used to dequeue nodes, (as seen above). Consequently, replacing node = q.popleft() with node = q.pop() would make a LIFO stack, resulting in a right-favored, pre-ordered DFS: ['a', 'c', 'f', 'b', 'e', 'd'].
you don't need to have two classes
class Tree:
val = None
left = None
right = None
def __init__(self, val):
self.val = val
def insert(self, val):
if self.val is not None:
if val < self.val:
if self.left is not None:
self.left.insert(val)
else:
self.left = Tree(val)
elif val > self.val:
if self.right is not None:
self.right.insert(val)
else:
self.right = Tree(val)
else:
return
else:
self.val = val
print("new node added")
def showTree(self):
if self.left is not None:
self.left.showTree()
print(self.val, end = ' ')
if self.right is not None:
self.right.showTree()
It is better to have two classes. That is better implementation –
Brunella
@Brunella 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. –
Frameup
the original poster only asked for a binary tree implementation and not a binary search tree... –
Frameup
(@Frameup
original poster only asked for a binary tree apropos something deleted?) –
Turntable A little more "Pythonic" ?
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def __repr__(self):
return str(self.value)
class BST:
def __init__(self):
self.root = None
def __repr__(self):
self.sorted = []
self.get_inorder(self.root)
return str(self.sorted)
def get_inorder(self, node):
if node:
self.get_inorder(node.left)
self.sorted.append(str(node.value))
self.get_inorder(node.right)
def add(self, value):
if not self.root:
self.root = Node(value)
else:
self._add(self.root, value)
def _add(self, node, value):
if value <= node.value:
if node.left:
self._add(node.left, value)
else:
node.left = Node(value)
else:
if node.right:
self._add(node.right, value)
else:
node.right = Node(value)
from random import randint
bst = BST()
for i in range(100):
bst.add(randint(1, 1000))
print (bst)
#!/usr/bin/python
class BinaryTree:
def __init__(self, left, right, data):
self.left = left
self.right = right
self.data = data
def pre_order_traversal(root):
print(root.data, end=' ')
if root.left != None:
pre_order_traversal(root.left)
if root.right != None:
pre_order_traversal(root.right)
def in_order_traversal(root):
if root.left != None:
in_order_traversal(root.left)
print(root.data, end=' ')
if root.right != None:
in_order_traversal(root.right)
def post_order_traversal(root):
if root.left != None:
post_order_traversal(root.left)
if root.right != None:
post_order_traversal(root.right)
print(root.data, end=' ')
The pre-order traversal is wrong: you need to test each branch separately. –
Neighboring
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 –
Rightminded
The way it was, if the left child was None, it wouldn't even look at the right child. –
Neighboring
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. –
Pathan
I know many good solutions have already been posted but I usually have a different approach for binary trees: going with some Node class and implementing it directly is more readable but when you have a lot of nodes it can become very greedy regarding memory, so I suggest adding one layer of complexity and storing the nodes in a python list, and then simulating a tree behavior using only the list.
You can still define a Node class to finally represent the nodes in the tree when needed, but keeping them in a simple form [value, left, right] in a list will use half the memory or less!
Here is a quick example of a Binary Search Tree class storing the nodes in an array. It provides basic fonctions such as add, remove, find...
"""
Basic Binary Search Tree class without recursion...
"""
__author__ = "@fbparis"
class Node(object):
__slots__ = "value", "parent", "left", "right"
def __init__(self, value, parent=None, left=None, right=None):
self.value = value
self.parent = parent
self.left = left
self.right = right
def __repr__(self):
return "<%s object at %s: parent=%s, left=%s, right=%s, value=%s>" % (self.__class__.__name__, hex(id(self)), self.parent, self.left, self.right, self.value)
class BinarySearchTree(object):
__slots__ = "_tree"
def __init__(self, *args):
self._tree = []
if args:
for x in args[0]:
self.add(x)
def __len__(self):
return len(self._tree)
def __repr__(self):
return "<%s object at %s with %d nodes>" % (self.__class__.__name__, hex(id(self)), len(self))
def __str__(self, nodes=None, level=0):
ret = ""
if nodes is None:
if len(self):
nodes = [0]
else:
nodes = []
for node in nodes:
if node is None:
continue
ret += "-" * level + " %s\n" % self._tree[node][0]
ret += self.__str__(self._tree[node][2:4], level + 1)
if level == 0:
ret = ret.strip()
return ret
def __contains__(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
return False
return True
return False
def __eq__(self, other):
return self._tree == other._tree
def add(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
b = self._tree[node_index][2]
k = 2
else:
b = self._tree[node_index][3]
k = 3
if b is None:
self._tree[node_index][k] = len(self)
self._tree.append([value, node_index, None, None])
break
node_index = b
else:
self._tree.append([value, None, None, None])
def remove(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
raise KeyError
if self._tree[node_index][2] is not None:
b, d = 2, 3
elif self._tree[node_index][3] is not None:
b, d = 3, 2
else:
i = node_index
b = None
if b is not None:
i = self._tree[node_index][b]
while self._tree[i][d] is not None:
i = self._tree[i][d]
p = self._tree[i][1]
b = self._tree[i][b]
if p == node_index:
self._tree[p][5-d] = b
else:
self._tree[p][d] = b
if b is not None:
self._tree[b][1] = p
self._tree[node_index][0] = self._tree[i][0]
else:
p = self._tree[i][1]
if p is not None:
if self._tree[p][2] == i:
self._tree[p][2] = None
else:
self._tree[p][3] = None
last = self._tree.pop()
n = len(self)
if i < n:
self._tree[i] = last[:]
if last[2] is not None:
self._tree[last[2]][1] = i
if last[3] is not None:
self._tree[last[3]][1] = i
if self._tree[last[1]][2] == n:
self._tree[last[1]][2] = i
else:
self._tree[last[1]][3] = i
else:
raise KeyError
def find(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
return None
return Node(*self._tree[node_index])
return None
I've added a parent attribute so that you can remove any node and maintain the BST structure.
Sorry for the readability, especially for the "remove" function. Basically, when a node is removed, we pop the tree array and replace it with the last element (except if we wanted to remove the last node). To maintain the BST structure, the removed node is replaced with the max of its left children or the min of its right children and some operations have to be done in order to keep the indexes valid but it's fast enough.
I used this technique for more advanced stuff to build some big words dictionaries with an internal radix trie and I was able to divide memory consumption by 7-8 (you can see an example here: https://gist.github.com/fbparis/b3ddd5673b603b42c880974b23db7cda)
import random
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.p = None
class BinaryTree:
def __init__(self):
self.root = None
def length(self):
return self.size
def inorder(self, node):
if node == None:
return None
else:
self.inorder(node.left)
print node.key,
self.inorder(node.right)
def search(self, k):
node = self.root
while node != None:
if node.key == k:
return node
if node.key > k:
node = node.left
else:
node = node.right
return None
def minimum(self, node):
x = None
while node.left != None:
x = node.left
node = node.left
return x
def maximum(self, node):
x = None
while node.right != None:
x = node.right
node = node.right
return x
def successor(self, node):
parent = None
if node.right != None:
return self.minimum(node.right)
parent = node.p
while parent != None and node == parent.right:
node = parent
parent = parent.p
return parent
def predecessor(self, node):
parent = None
if node.left != None:
return self.maximum(node.left)
parent = node.p
while parent != None and node == parent.left:
node = parent
parent = parent.p
return parent
def insert(self, k):
t = TreeNode(k)
parent = None
node = self.root
while node != None:
parent = node
if node.key > t.key:
node = node.left
else:
node = node.right
t.p = parent
if parent == None:
self.root = t
elif t.key < parent.key:
parent.left = t
else:
parent.right = t
return t
def delete(self, node):
if node.left == None:
self.transplant(node, node.right)
elif node.right == None:
self.transplant(node, node.left)
else:
succ = self.minimum(node.right)
if succ.p != node:
self.transplant(succ, succ.right)
succ.right = node.right
succ.right.p = succ
self.transplant(node, succ)
succ.left = node.left
succ.left.p = succ
def transplant(self, node, newnode):
if node.p == None:
self.root = newnode
elif node == node.p.left:
node.p.left = newnode
else:
node.p.right = newnode
if newnode != None:
newnode.p = node.p
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 –
Hershey
This implementation supports insert, find and delete operations without destroy the structure of the tree. This is not a banlanced tree.
# Class for construct the nodes of the tree. (Subtrees)
class Node:
def __init__(self, key, parent_node = None):
self.left = None
self.right = None
self.key = key
if parent_node == None:
self.parent = self
else:
self.parent = parent_node
# Class with the structure of the tree.
# This Tree is not balanced.
class Tree:
def __init__(self):
self.root = None
# Insert a single element
def insert(self, x):
if(self.root == None):
self.root = Node(x)
else:
self._insert(x, self.root)
def _insert(self, x, node):
if(x < node.key):
if(node.left == None):
node.left = Node(x, node)
else:
self._insert(x, node.left)
else:
if(node.right == None):
node.right = Node(x, node)
else:
self._insert(x, node.right)
# Given a element, return a node in the tree with key x.
def find(self, x):
if(self.root == None):
return None
else:
return self._find(x, self.root)
def _find(self, x, node):
if(x == node.key):
return node
elif(x < node.key):
if(node.left == None):
return None
else:
return self._find(x, node.left)
elif(x > node.key):
if(node.right == None):
return None
else:
return self._find(x, node.right)
# Given a node, return the node in the tree with the next largest element.
def next(self, node):
if node.right != None:
return self._left_descendant(node.right)
else:
return self._right_ancestor(node)
def _left_descendant(self, node):
if node.left == None:
return node
else:
return self._left_descendant(node.left)
def _right_ancestor(self, node):
if node.key <= node.parent.key:
return node.parent
else:
return self._right_ancestor(node.parent)
# Delete an element of the tree
def delete(self, x):
node = self.find(x)
if node == None:
print(x, "isn't in the tree")
else:
if node.right == None:
if node.left == None:
if node.key < node.parent.key:
node.parent.left = None
del node # Clean garbage
else:
node.parent.right = None
del Node # Clean garbage
else:
node.key = node.left.key
node.left = None
else:
x = self.next(node)
node.key = x.key
x = None
# tests
t = Tree()
t.insert(5)
t.insert(8)
t.insert(3)
t.insert(4)
t.insert(6)
t.insert(2)
t.delete(8)
t.delete(5)
t.insert(9)
t.insert(1)
t.delete(2)
t.delete(100)
# Remember: Find method return the node object.
# To return a number use t.find(nº).key
# But it will cause an error if the number is not in the tree.
print(t.find(5))
print(t.find(8))
print(t.find(4))
print(t.find(6))
print(t.find(9))
A good implementation of binary search tree, taken from here:
'''
A binary search Tree
'''
from __future__ import print_function
class Node:
def __init__(self, label, parent):
self.label = label
self.left = None
self.right = None
#Added in order to delete a node easier
self.parent = parent
def getLabel(self):
return self.label
def setLabel(self, label):
self.label = label
def getLeft(self):
return self.left
def setLeft(self, left):
self.left = left
def getRight(self):
return self.right
def setRight(self, right):
self.right = right
def getParent(self):
return self.parent
def setParent(self, parent):
self.parent = parent
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, label):
# Create a new Node
new_node = Node(label, None)
# If Tree is empty
if self.empty():
self.root = new_node
else:
#If Tree is not empty
curr_node = self.root
#While we don't get to a leaf
while curr_node is not None:
#We keep reference of the parent node
parent_node = curr_node
#If node label is less than current node
if new_node.getLabel() < curr_node.getLabel():
#We go left
curr_node = curr_node.getLeft()
else:
#Else we go right
curr_node = curr_node.getRight()
#We insert the new node in a leaf
if new_node.getLabel() < parent_node.getLabel():
parent_node.setLeft(new_node)
else:
parent_node.setRight(new_node)
#Set parent to the new node
new_node.setParent(parent_node)
def delete(self, label):
if (not self.empty()):
#Look for the node with that label
node = self.getNode(label)
#If the node exists
if(node is not None):
#If it has no children
if(node.getLeft() is None and node.getRight() is None):
self.__reassignNodes(node, None)
node = None
#Has only right children
elif(node.getLeft() is None and node.getRight() is not None):
self.__reassignNodes(node, node.getRight())
#Has only left children
elif(node.getLeft() is not None and node.getRight() is None):
self.__reassignNodes(node, node.getLeft())
#Has two children
else:
#Gets the max value of the left branch
tmpNode = self.getMax(node.getLeft())
#Deletes the tmpNode
self.delete(tmpNode.getLabel())
#Assigns the value to the node to delete and keesp tree structure
node.setLabel(tmpNode.getLabel())
def getNode(self, label):
curr_node = None
#If the tree is not empty
if(not self.empty()):
#Get tree root
curr_node = self.getRoot()
#While we don't find the node we look for
#I am using lazy evaluation here to avoid NoneType Attribute error
while curr_node is not None and curr_node.getLabel() is not label:
#If node label is less than current node
if label < curr_node.getLabel():
#We go left
curr_node = curr_node.getLeft()
else:
#Else we go right
curr_node = curr_node.getRight()
return curr_node
def getMax(self, root = None):
if(root is not None):
curr_node = root
else:
#We go deep on the right branch
curr_node = self.getRoot()
if(not self.empty()):
while(curr_node.getRight() is not None):
curr_node = curr_node.getRight()
return curr_node
def getMin(self, root = None):
if(root is not None):
curr_node = root
else:
#We go deep on the left branch
curr_node = self.getRoot()
if(not self.empty()):
curr_node = self.getRoot()
while(curr_node.getLeft() is not None):
curr_node = curr_node.getLeft()
return curr_node
def empty(self):
if self.root is None:
return True
return False
def __InOrderTraversal(self, curr_node):
nodeList = []
if curr_node is not None:
nodeList.insert(0, curr_node)
nodeList = nodeList + self.__InOrderTraversal(curr_node.getLeft())
nodeList = nodeList + self.__InOrderTraversal(curr_node.getRight())
return nodeList
def getRoot(self):
return self.root
def __isRightChildren(self, node):
if(node == node.getParent().getRight()):
return True
return False
def __reassignNodes(self, node, newChildren):
if(newChildren is not None):
newChildren.setParent(node.getParent())
if(node.getParent() is not None):
#If it is the Right Children
if(self.__isRightChildren(node)):
node.getParent().setRight(newChildren)
else:
#Else it is the left children
node.getParent().setLeft(newChildren)
#This function traversal the tree. By default it returns an
#In order traversal list. You can pass a function to traversal
#The tree as needed by client code
def traversalTree(self, traversalFunction = None, root = None):
if(traversalFunction is None):
#Returns a list of nodes in preOrder by default
return self.__InOrderTraversal(self.root)
else:
#Returns a list of nodes in the order that the users wants to
return traversalFunction(self.root)
#Returns an string of all the nodes labels in the list
#In Order Traversal
def __str__(self):
list = self.__InOrderTraversal(self.root)
str = ""
for x in list:
str = str + " " + x.getLabel().__str__()
return str
def InPreOrder(curr_node):
nodeList = []
if curr_node is not None:
nodeList = nodeList + InPreOrder(curr_node.getLeft())
nodeList.insert(0, curr_node.getLabel())
nodeList = nodeList + InPreOrder(curr_node.getRight())
return nodeList
def testBinarySearchTree():
r'''
Example
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
'''
r'''
Example After Deletion
7
/ \
1 4
'''
t = BinarySearchTree()
t.insert(8)
t.insert(3)
t.insert(6)
t.insert(1)
t.insert(10)
t.insert(14)
t.insert(13)
t.insert(4)
t.insert(7)
#Prints all the elements of the list in order traversal
print(t.__str__())
if(t.getNode(6) is not None):
print("The label 6 exists")
else:
print("The label 6 doesn't exist")
if(t.getNode(-1) is not None):
print("The label -1 exists")
else:
print("The label -1 doesn't exist")
if(not t.empty()):
print(("Max Value: ", t.getMax().getLabel()))
print(("Min Value: ", t.getMin().getLabel()))
t.delete(13)
t.delete(10)
t.delete(8)
t.delete(3)
t.delete(6)
t.delete(14)
#Gets all the elements of the tree In pre order
#And it prints them
list = t.traversalTree(InPreOrder, t.root)
for x in list:
print(x)
if __name__ == "__main__":
testBinarySearchTree()
Although I like the answer from "djra", I'm not a big fan of recursion, as it's usually slower than a simple loop and less readable.
A binary tree without recursion is roughly:
- 72% faster when adding new nodes
- 27% faster when finding a node
My implementation:
class Node:
def __init__(self, val) -> None:
self.val = val
self.left = None
self.right = None
class Tree:
def __init__(self) -> None:
self.root = None
def add(self, val):
if self.root is None:
self.root = Node(val)
return
current_node = self.root
while current_node is not None:
# too many nested conditionals, you could move it into a separated
# method for readibility purposes
if val < current_node.val:
if current_node.left is None:
current_node.left = Node(val)
break
else:
current_node = current_node.left
else:
if current_node.right is None:
current_node.right = Node(val)
break
else:
current_node = current_node.right
def find(self, val):
current_node = self.root
while current_node is not None:
if val < current_node.val:
current_node = current_node.left
elif val > current_node.val:
current_node = current_node.right
else:
return current_node
raise ValueError("Node does not exist")
def add_with_recursion(self, val):
if self.root is None:
self.root = Node(val)
else:
self._add_with_recursion(val, self.root)
def _add_with_recursion(self, val, node):
if val < node.val:
if node.left is not None:
self._add_with_recursion(val, node.left)
else:
node.left = Node(val)
else:
if node.right is not None:
self._add_with_recursion(val, node.right)
else:
node.right = Node(val)
def find_with_recursion(self, val):
if self.root is not None:
return self._find_with_recursion(val, self.root)
else:
return None
def _find_with_recursion(self, val, node):
if val == node.val:
return node
elif val < node.val and node.left is not None:
return self._find_with_recursion(val, node.left)
elif val > node.val and node.right is not None:
return self._find_with_recursion(val, node.right)
Speed:
p.s.: i just multiplied the result of timeit because 500 was the maximum number of timeit's i could achieve without exceeding the max recursion depth
import timeit
values = [10, 7, 14, 8, 12, 9, 2, 1, 5, 3, 14, 0.5]
def add_with_rec(tree_with_recursion, values):
for i in values:
tree_with_recursion.add_with_recursion(i)
return tree_with_recursion
def add(tree, values):
for i in values:
tree.add(i)
return tree
# Measuring with recursion
tree_with_recursion = Tree()
print("\nAdding with recursion:")
print(
100000
* timeit.timeit(lambda: add_with_rec(tree_with_recursion, values), number=500)
)
print("\nFinding with recursion:")
print(
100000
* timeit.timeit(lambda: tree_with_recursion.find_with_recursion(0.5), number=500)
)
# Measuring without recursion
tree = Tree()
print("\nAdding without recursion:")
print(100000 * timeit.timeit(lambda: add(tree, values), number=500))
print("\nFinding wihtout recursion:")
print(100000 * timeit.timeit(lambda: tree.find(0.5), number=500))
Output:
Adding with recursion:
13253.60000191722
Finding with recursion:
37.02999965753406
Adding without recursion:
3672.5399986607954
Finding wihtout recursion:
27.779999072663486
I want to show a variation of @apadana's method, which is more useful when there is a considerable number of nodes:
'''
Suppose we have the following tree
10
/ \
11 9
/ \ / \
7 12 15 8
'''
# Step 1 - Create nodes - Use a list instead of defining each node separately
nlist = [10,11,7,9,15,8,12]; n = []
for i in range(len(nlist)): n.append(Node(nlist[i]))
# Step 2 - Set each node position
n[0].left = n[1]
n[1].left = n[2]
n[0].right = n[3]
n[3].left = n[4]
n[3].right = n[5]
n[1].right = n[6]
You can make your own BinaryTree data structure in Python the OOP way (or building a class). You can separate two class in here: Node and BinaryTree. The "Node" class will be responsible for creating individual node objects for the BinaryTree while the "BinaryTree" class is what you'll need to implement the binary tree on top of the "Node" class.
Here's what I coded when I'm studying it back then:
class TreeNode:
def __init__(self, data=None):
self.data = data
self.left = None
self.right = None
def __str__(self):
return f'Node(Data={self.data}, Left={self.left}, Right={self.right})'
def __repr__(self):
return self.__str__()
def get_data(self):
return self.data
def set_data(self, data):
self.data = data
def get_left(self):
return self.left
def set_left(self, left):
self.left = left
def get_right(self):
return self.right
def set_right(self, right):
self.right = right
class BinaryTree:
def __init__(self, root=None):
self.root = TreeNode(root)
def __str__(self):
return f'BinaryTree({self.root})'
def __repr__(self):
return f'BinaryTree({self.root})'
def insert(self, data):
# if empty tree
if self.root.get_data() is None:
return self.root.set_data(data)
new_node = TreeNode(data)
current = self.root
while True:
if data < current.get_data():
if current.get_left() is None:
return current.set_left(new_node)
current = current.get_left()
continue
elif data > current.get_data():
if current.get_right() is None:
return current.set_right(new_node)
current = current.get_right()
continue
return
# still needs other methods like the delete method, but you can
# try it out yourself
def delete(self, node):
pass
def main():
myTree = BinaryTree()
myTree.insert(5)
myTree.insert(3)
myTree.insert(4)
myTree.insert(2)
myTree.insert(8)
myTree.insert(9)
myTree.insert(6)
print(myTree)
if __name__ == '__main__':
main()
This is a Binary Search Tree, which is a subset of a Binary Tree, where the left node is less than the right. –
Antisepsis
The left child precedes the right child in order of Nodes.
Each node is considered to be the root node of the left and right tree. Write a class to create nodes easily:
class _Node:
#slots are class level member,efficiently allocates memory for instance variables
__slots__='_element','_left','_right'
def __init__(self,element,left=None,right=None):
# left is not a node, left is the left sub Binary Tree
# right is the right sub Binary Tree
self._element=element
self._left=left
self._right=right
Here we write the Binary class:
class BinaryTree:
def __init__(self):
self._root=None
def make_tree(self,e,left,right): # left=left-subtree, right=right-subtree
# we start the tree from leaf nodes.. since it has no left and right subtrees, left and right null
# x.maketree(B,null,null)=[Q,B,Q] this is node x
# y.maketree(C,null,null)=[Q,C,Q]
# z.maketree(A,x,y) "z" is the parent of "x" and "y"
# each node is the root of the binary tree
# each subtree is also considered to be Binary Tree
self._root=_Node(e,left._root,right._root)
# inorder similar to infix:A+B. visit left first, then root, then right
def inorder(self,troot):
if troot:
self.inorder(troot._left)
print(troot._element,end=' ')
self.inorder(troot._right)
# preorder similar to prefix. +AB, visit root first,then left, then right
def preorder(self,troot):
if troot:
print(troot._element,end=' ')
self.preorder(troot._left)
self.preorder(troot._right)
# postorder similar to postfix. left first, then right, then root
def postorder(self,troot):
if troot:
self.postorder(troot._left)
self.postorder(troot._right)
print(troot._element,end=' ')
# count the number of nodes recursively
# recursive calls break the problem into smallest sub problems
# we are recursively asking each node, how many children does each node have
# if a node does not have any child, we count that node, that is why add +1. x+y+1
def count(self,troot):
if troot:
x=self.count(troot._left)
print("x",x)
y=self.count(troot._right)
print("y",y)
print("x+y",x+y)
# we add +1 because we have to count the root
return x+y+1
return 0
def height(self,troot):
if troot:
x=self.height(troot._left)
y=self.height(troot._right)
if x>y:
return x+1
else:
return y+1
return 0
now create the binary tree:
creating 6 sub binary trees
x=BinaryTree()
y=BinaryTree()
z=BinaryTree()
r=BinaryTree()
s=BinaryTree()
t=BinaryTree()
a=BinaryTree() # null binary tree
first make leaf nodes, 40 and 60
# if a tree has only root node, it is still binary tree
x.make_tree(40,a,a)
y.make_tree(60,a,a)
creating internal nodes
z.make_tree(20,x,a) #left internal
r.make_tree(50,a,y) #right internal
s.make_tree(30,r,a)
t.make_tree(10,z,s)
Below a proposed fix to the Binary Search Tree implementation from djra,
which I think mostly works except for printTree().
Expectation is:
3
0 4
2 8
But actual print out is:
0
2
3
4
8
Below fixed code:
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
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 = TreeNode(val)
else:
self._add(val, self.root)
def _add(self, val, node):
if val < node.val:
if node.left is not None:
self._add(val, node.left)
else:
node.left = TreeNode(val)
else:
if node.right is not None:
self._add(val, node.right)
else:
node.right = TreeNode(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.val:
return node
elif (val < node.val and node.left is not None):
return self._find(val, node.left)
elif (val > node.val and node.right is not None):
return self._find(val, node.right)
def deleteTree(self):
self.root = None
def printTree(self):
if self.root is not None:
self._printTree(self.root, 0)
def _printTree(self, node, level):
if node is not None:
self._printTree(node.right, level + 1)
print(' ' * level + str(node.val))
self._printTree(node.left, level + 1)
It's printing the tree sideways rather than downwards:
8
4
3
2
0
Well... if one of you genius can make this print vertically that'd be nice.
What question does this answer? –
Turntable
Binary Tree in Python
class Tree(object):
def __init__(self):
self.data=None
self.left=None
self.right=None
def insert(self, x, root):
if root==None:
t=node(x)
t.data=x
t.right=None
t.left=None
root=t
return root
elif x<root.data:
root.left=self.insert(x, root.left)
else:
root.right=self.insert(x, root.right)
return root
def printTree(self, t):
if t==None:
return
self.printTree(t.left)
print t.data
self.printTree(t.right)
class node(object):
def __init__(self, x):
self.x=x
bt=Tree()
root=None
n=int(raw_input())
a=[]
for i in range(n):
a.append(int(raw_input()))
for i in range(n):
root=bt.insert(a[i], root)
bt.printTree(root)
Here is a simple solution which can be used to build a binary tree using a recursive approach to display the tree in order traversal has been used in the below code.
class Node(object):
def __init__(self):
self.left = None
self.right = None
self.value = None
@property
def get_value(self):
return self.value
@property
def get_left(self):
return self.left
@property
def get_right(self):
return self.right
@get_left.setter
def set_left(self, left_node):
self.left = left_node
@get_value.setter
def set_value(self, value):
self.value = value
@get_right.setter
def set_right(self, right_node):
self.right = right_node
def create_tree(self):
_node = Node() #creating new node.
_x = input("Enter the node data(-1 for null)")
if(_x == str(-1)): #for defining no child.
return None
_node.set_value = _x #setting the value of the node.
print("Enter the left child of {}".format(_x))
_node.set_left = self.create_tree() #setting the left subtree
print("Enter the right child of {}".format(_x))
_node.set_right = self.create_tree() #setting the right subtree.
return _node
def pre_order(self, root):
if root is not None:
print(root.get_value)
self.pre_order(root.get_left)
self.pre_order(root.get_right)
if __name__ == '__main__':
node = Node()
root_node = node.create_tree()
node.pre_order(root_node)
Code taken from : Binary Tree in Python
© 2022 - 2024 — McMap. All rights reserved.