How to implement a binary tree?
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() 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.
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)
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.
[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.
# 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
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Реализация двоичного дерева питон = BinaryTreeNode(key) # invariant: self.nodesРеализация двоичного дерева питон exists # handle left child if left_key is None: self.nodesРеализация двоичного дерева питон.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Реализация двоичного дерева питон.left = self.nodes[left_key] # handle right child if right_key == None: self.nodesРеализация двоичного дерева питон.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Реализация двоичного дерева питон.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Реализация двоичного дерева питон # 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