A Tree is any data structure that follows some particular rules. The tree must have exactly one root node. If you have two root nodes, what you actually have is two trees. One tree has one root, and one root equals one tree. Additionally, each node can have any number of child nodes or may have zero children, in which case we call that node a leaf. A node can have 100 children or more and still be a valid tree. Each node, except for the root, links to exactly one parent. If you have a child with two parents, then loops get introduced and cause all kinds of problems. A node cannot be its own parent. If your data structure meets these criteria, then it is a tree.
About Trees
There are many different types of trees with additional rules that make them useful. Oftentimes each node in a tree usually has some kind of data associated with it. Think of the DOM in web development or a directory structure within an operating system. In our case, we’ll be talking about the binary search tree. In a binary search tree, each node has only two children called a left and a right child. This is what makes it a binary(two) tree. Each node has a value associated with it. Values to the left of the node must be less than the value of their parents. Values to the right of the node must be greater than the value of their parents. BSTs may not equal values, each value must be unique.
Building A Tree
The code below implements a tree via the Node class. This is a basic building block of our trees. We can pass some data to it when it’s initialized. Each node will have a number that the node represents. In addition to the Node, we have some data and properties of left and right children. With the basic structure implemented, we then start building a tree. We can attach new nodes to the left and right of our parent node. So node.left equals node 15, node.right equals 25. Note that I’m putting nodes with smaller data, in this case, the 15 to the left and I’m putting nodes with larger data, in this case, the 25 to the right. This is because we’re building a binary search tree and smaller values always go to the left, larger values go to the right. Expanding the tree a little more, we set node.left.left equals 12 and that’s going to be our smallest number in the tree. Node.left.right is set to 16. Node.right.left is set to 23. Node.right.right is set to 100. Then you can see how we are able to access values at any point in the tree.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class Tree:
def __init__(self, root, name=''):
self.root = root
self.name = name
node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)
nice_tree = Tree(node, 'A real nice Tree.')
print(nice_tree.name)
print(nice_tree.root.data)
print(nice_tree.root.left.data)
print(nice_tree.root.right.right.data)A real nice Tree. 20 15 100
How To Search A Tree
In this section, we can add search to the tree knowing that small values always go to the left and the large values always go to the right. The search method is going to take in a target, which is the data that we’re looking for in the tree. The first thing we’re going to do is check if the current node matches the target that we’re searching for. If self.data equals target, then we found what we were looking for. By returning the node that we found in the tree, we can stop the search. Otherwise, if no match is found, we need to keep looking. We do this by recursively checking the left and right sides of the tree.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def search(self, target):
if self.data == target:
print("Found the value!")
return self
if self.left and self.data > target:
return self.left.search(target)
if self.right and self.data < target:
return self.right.search(target)
print("Value is not in tree")
class Tree:
def __init__(self, root, name=''):
self.root = root
self.name = name
def search(self, target):
return self.root.search(target)
node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)
nice_tree = Tree(node, 'A real nice Tree')
result = nice_tree.search(23)
if result:
print(f'{result.data} is in the "{nice_tree.name}" tree')Found the value! 23 is in the "A real nice Tree" tree
How To Traverse A Tree
Three common algorithms to traverse a tree include Traverse In Order, Traverse Pre Order, and Traverse Post Order. You can read the specifics of how they work at the links cited. The code for our implementation is below.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def search(self, target):
if self.data == target:
print("Found it!")
return self
if self.left and self.data > target:
return self.left.search(target)
if self.right and self.data < target:
return self.right.search(target)
print("Value is not in tree")
def traversePreorder(self):
print(self.data)
if self.left:
self.left.traversePreorder()
if self.right:
self.right.traversePreorder()
def traverseInorder(self):
if self.left:
self.left.traverseInorder()
print(self.data)
if self.right:
self.right.traverseInorder()
def traversePostorder(self):
if self.left:
self.left.traversePostorder()
if self.right:
self.right.traversePostorder()
print(self.data)
class Tree:
def __init__(self, root, name=''):
self.root = root
self.name = name
def search(self, target):
return self.root.search(target)
node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)
node.traversePreorder()
print('-' * 20)
node.traverseInorder()
print('-' * 20)
node.traversePostorder()20 15 12 16 25 23 100 -------------------- 12 15 16 20 23 25 100 -------------------- 12 16 15 23 100 25 20
Get The Max Height
The height of a tree is how many nodes there are from the root to the leaf at the deepest part of the tree. The height of a tree is its maximum height. The height is important because it determines the maximum run time for the search of a tree. To find the maximum height of a tree is done with a small recursive function shown here.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def search(self, target):
if self.data == target:
print("Found it!")
return self
if self.left and self.data > target:
return self.left.search(target)
if self.right and self.data < target:
return self.right.search(target)
print("Value is not in tree")
def height(self, h=0):
leftHeight = self.left.height(h + 1) if self.left else h
rightHeight = self.right.height(h + 1) if self.right else h
return max(leftHeight, rightHeight)
class Tree:
def __init__(self, root, name=''):
self.root = root
self.name = name
def search(self, target):
return self.root.search(target)
def height(self):
return self.root.height()
node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)
print(node.height())2
Get Nodes From A Given Depth
In this section, we have a function that takes in an arbitrary depth, like two, and prints out the nodes at that depth from left to right. This is a useful thing to have if you want to print out the entire contents of the tree.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def traversePreorder(self):
print(self.data)
if self.left:
self.left.traversePreorder()
if self.right:
self.right.traversePreorder()
def traverseInorder(self):
if self.left:
self.left.traverseInorder()
print(self.data)
if self.right:
self.right.traverseInorder()
def traversePostorder(self):
if self.left:
self.left.traversePostorder()
if self.right:
self.right.traversePostorder()
print(self.data)
def search(self, target):
if self.data == target:
print("Found it!")
return self
if self.left and self.data > target:
return self.left.search(target)
if self.right and self.data < target:
return self.right.search(target)
print("Value is not in tree")
def getNodesAtDepth(self, depth, nodes=[]):
if depth == 0:
nodes.append(self.data)
return nodes
if self.left:
self.left.getNodesAtDepth(depth - 1, nodes)
else:
nodes.extend([None] * 2 ** (depth - 1))
if self.right:
self.right.getNodesAtDepth(depth - 1, nodes)
else:
nodes.extend([None] * 2 ** (depth - 1))
return nodes
def height(self, h=0):
leftHeight = self.left.height(h + 1) if self.left else h
rightHeight = self.right.height(h + 1) if self.right else h
return max(leftHeight, rightHeight)
class Tree:
def __init__(self, root, name=''):
self.root = root
self.name = name
def traverseInorder(self):
self.root.traverseInorder()
def traversePreorder(self):
self.root.traversePreorder()
def traversePostorder(self):
self.root.traversePostorder()
def search(self, target):
return self.root.search(target)
def getNodesAtDepth(self, depth):
return self.root.getNodesAtDepth(depth)
def height(self):
return self.root.height()
node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)
print(node.getNodesAtDepth(0))
print(node.getNodesAtDepth(1))
print(node.getNodesAtDepth(2))[20] [20, 15, 25] [20, 15, 25, 12, 16, 23, 100]
Printing A Tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def traversePreorder(self):
print(self.data)
if self.left:
self.left.traversePreorder()
if self.right:
self.right.traversePreorder()
def traverseInorder(self):
if self.left:
self.left.traverseInorder()
print(self.data)
if self.right:
self.right.traverseInorder()
def traversePostorder(self):
if self.left:
self.left.traversePostorder()
if self.right:
self.right.traversePostorder()
print(self.data)
def search(self, target):
if self.data == target:
print("Found it!")
return self
if self.left and self.data > target:
return self.left.search(target)
if self.right and self.data < target:
return self.right.search(target)
print("Value is not in tree")
def getNodesAtDepth(self, depth, nodes=[]):
if depth == 0:
nodes.append(self.data)
return nodes
if self.left:
self.left.getNodesAtDepth(depth - 1, nodes)
else:
nodes.extend([None] * 2 ** (depth - 1))
if self.right:
self.right.getNodesAtDepth(depth - 1, nodes)
else:
nodes.extend([None] * 2 ** (depth - 1))
return nodes
def height(self, h=0):
leftHeight = self.left.height(h + 1) if self.left else h
rightHeight = self.right.height(h + 1) if self.right else h
return max(leftHeight, rightHeight)
class Tree:
def __init__(self, root, name=''):
self.root = root
self.name = name
def _nodeToChar(self, n, spacing):
if n is None:
return '_' + (' ' * spacing)
spacing = spacing - len(str(n)) + 1
return str(n) + (' ' * spacing)
def print(self, label=''):
print(self.name + ' ' + label)
height = self.root.height()
spacing = 3
width = int((2 ** height - 1) * (spacing + 1) + 1)
# Root offset
offset = int((width - 1) / 2)
for depth in range(0, height + 1):
if depth > 0:
# print directional lines
print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\'] * (2 ** (depth - 1))))
row = self.root.getNodesAtDepth(depth, [])
print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))
spacing = offset + 1
offset = int(offset / 2) - 1
print('')
def traverseInorder(self):
self.root.traverseInorder()
def traversePreorder(self):
self.root.traversePreorder()
def traversePostorder(self):
self.root.traversePostorder()
def search(self, target):
return self.root.search(target)
def getNodesAtDepth(self, depth):
return self.root.getNodesAtDepth(depth)
def height(self):
return self.root.height()
tree = Tree(Node(20))
tree.root.left = Node(15)
tree.root.right = Node(25)
tree.root.left.left = Node(12)
tree.root.left.right = Node(16)
tree.root.right.left = Node(23)
tree.root.right.right = Node(100)
tree.print()20 / \ 15 25 / \ / \ 12 16 23 100
Python Binary Search Tree Summary
In this tutorial, we learned about binary trees and reviewed some useful applications of this data structure. A binary tree is a tree data structure made up of nodes with at most two children. Each node can have a right and left child. The node at the top is referred to as the root node. A node without children is known as a leaf node. Most applications use different types of binary trees such as tries, binary search trees, and B-trees. In computer science, binary trees are often used for searching and sorting since they provide a means to store data hierarchically. Common operations that can be used on binary trees include insertion, deletion, and traversal.
Getting Started with MacOS: A Beginner’s Guide
What Is the Metaverse and How Will It Shape Our Digital Future
6 Steps To Achieve Whatever You Want
Add Featured Image Support To Your WordPress Theme
What Is Garbage Collection In Python
Python Basics For Beginners
Python Lists
Python Dictionary Tutorial