Introduction of Binary Search Tree in Python
Binary trees are a fundamental data structure in computer science. They are used to represent hierarchical data such as file systems family trees and organizational charts. A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. In this blog post we will discuss what binary trees are how they work and how to implement a binary tree search in Python.
What is a Binary Tree?
A binary tree is a hierarchical data structure in which each node has at most two children referred to as the left child and the right child. The topmost node of the tree is called the root and the nodes that have no children are called leaves. Each node of the binary tree contains a value and two pointers one to the left child and the other to the right child. The left child is always less than or equal to the parent and the right child is always greater than or equal to the parent.
3 Ways to Implement Binary Search in Python with Programming Examples
How does Binary Tree Search Work?
Binary tree search is a process of finding specific node in a binary tree. The algorithm start at the root node and compares the value to be searched with the value of the root node. If the value is less than root node value the algorithm moves to the left child of the root node. If the value is greater than the root node value the algorithm move to the right child of the root node. This process is repeated until value is found or until there are no more nodes to search.
Implementation of Binary Search Tree in Python
Now We will implement binary search tree in Python using recursive function that take the root node of binary tree and the value to be searched as argument. We will also create class for binary tree which have method to insert nodes and search for a specific node.
Here’s the Python code to implement a binary tree and search for a specific node in the tree:
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, data):
if self.root is None:
self.root = Node(data)
else:
self._insert(data, self.root)
def _insert(self, data, current_node):
if data < current_node.data:
if current_node.left is None:
current_node.left = Node(data)
else:
self._insert(data, current_node.left)
elif data > current_node.data:
if current_node.right is None:
current_node.right = Node(data)
else:
self._insert(data, current_node.right)
def search(self, value):
if self.root is None:
return False
else:
return self._search(value, self.root)
def _search(self, value, current_node):
if current_node is None:
return False
elif current_node.data == value:
return True
elif value < current_node.data:
return self._search(value, current_node.left)
else:
return self._search(value, current_node.right)
In above code we first define a Node class which represents a single node in the binary tree. Each Node object has a left and right attribute that point to the left and right children respectively. The data attribute stores the value of the node.
We then define a BinaryTree class which represents the binary tree data structure. The BinaryTree class has a root attribute that points to the root node of the tree. The insert() method of the BinaryTree class takes a value as an argument and inserts a new node with that value into the tree. If the root node is None then the new node becomes the root node. Otherwise the _insert() method is called with the current node and the value to be inserted as arguments. The _insert() method recursively searches the tree until it find the correct position to insert the new node.
The search() method of BinaryTree class takes a value as argument and searches the tree for a node with that value. If the root node is None then the value is not found and the method returns False. Otherwise the search() method is called with the current node and the value to be searched as arguments. The search() method recursively searches the tree until it finds the node with the correct value or determines that the value is not in the tree.
To create a binary tree and search for a specific node, we can use the following code:
# create a binary tree
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(9)
# search for a node
print(tree.search(7)) # True
print(tree.search(4)) # False
In above code we first create a new BinaryTree object and insert some nodes into the tree. We then call the search() method of the tree object with some values to search for. The search() method returns True if the value is found in the tree and False otherwise.
Conclusion
In this post we have discussed what binary trees are and how they work. We also implemented a binary tree search in Python using a recursive function and a BinaryTree class. With this implementation we can create a binary tree insert nodes and search for a specific node in the tree. Binary trees are a fundamental data structure that is used in many different applications and understanding how to work with them is an important skill for any programmer.
Program to Traverse a graph using the breadth first search in Python