Description:
A binary tree is a data structure in which each node has at most two children, referred to as the left
and right children.
It is a hierarchical structure used in many algorithms, particularly for searching and sorting.
Step-by-Step Process
Define a Node:
A node in a binary tree contains a value and pointers (or references) to its left and right child
nodes.
Create the Binary Tree:
The tree is constructed by linking nodes together.
Traversal:
A common operation on a binary tree is traversal, which involves visiting each node in a specific
order.
Insert Nodes:
New nodes can be inserted into the tree by comparing values and placing the node either in the left or right subtree
based on the comparison.
Search and Delete:
Operations such as searching for a value or deleting a node can be implemented recursively.
Sample Code
#Code for binary tree
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.value = key
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, value):
if self.root is None:
self.root = Node(value)
else:
self._insert_recursively(self.root, value)
def _insert_recursively(self, node, value):
if value < node.value:
if node.left is None:
node.left = Node(value)
else:
self._insert_recursively(node.left, value)
else:
if node.right is None:
node.right = Node(value)
else:
self._insert_recursively(node.right, value)
def inorder_traversal(self, node):
if node:
self.inorder_traversal(node.left)
print(node.value, end=" ")
self.inorder_traversal(node.right)
def search(self, value):
return self._search_recursively(self.root, value)
def _search_recursively(self, node, value):
if node is None or node.value == value:
return node
elif value < node.value:
return self._search_recursively(node.left, value)
else:
return self._search_recursively(node.right, value)
bt = BinaryTree()
bt.insert(10)
bt.insert(5)
bt.insert(20)
bt.insert(15)
bt.insert(3)
print("Output for binary tree:")
print("In-order Traversal:")
bt.inorder_traversal(bt.root)
result = bt.search(15)
if result:
print("\nValue found:", result.value)
else:
print("\nValue not found.")