Binary Tree Insertion simplified
Tree
Trees are nonlinear data structures composed of nodes that hold data. These nodes are connected by edges that define a parent and child relationship. Trees are nonlinear in that they are not organized sequentially, instead they are organized through relationships or hierarchy. The first node of a tree is called the root node and it can have zero or more child nodes.
What is Binary Tree ?
A binary tree can be defined as each node has a maximum of two children. BInary Search has consists of the following properties :
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example :
Node Class :
We need to represent a tree node. To do that, we create a new class named Node with 2 attributes:
- Left node
- Right node
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
Let’s create a tree node containing the integer 8.
root=Node(8)
Note that we just created a tree with a single node.
Insert :
This method is used to insert a new node in the tree
class Node:
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
Let’s add 3 nodes to our root node which we created above,
root.insert(3)
root.insert(10)
root.insert(1)
This is what happens when we add the second node (3):
- 1- root node’s method insert() is called with data = 3.
- 2- 3 is less than 8 and left child is None so we attach the new node to it.
This is what happens when we add the third node (10):
- 1- root node’s method insert() is called with data = 10.
- 2- 10 is greater than 8 and right child is None so we attach the new node to it.
This is what happens when we add the fourth node (1):
- 1- root node’s method insert() is called with data = 1.
- 2- 1 is less than 8 so the root’s left child (3) insert() method is called with data = 1. Note how we call the method on a subtree.
- 3- 1 is less than 3 and left child is None so we attach the new node to it.
Tree looks like :
Insert the remaining elements :
root.insert(6)
root.insert(4)
root.insert(7)
root.insert(14)
root.insert(13)
