- A Binary Tree is simply a data structure with a 'key' element, and two children, say 'left' and 'right'.
- A tree whose element has at most 2 children is called Binary Tree.
- In Binary tree, every element has at most 2 children only we typically name them the left and right child.
- A common kind of tree is a binary tree, in which each node contains a reference to two other nodes (possibly None)
- value - pointer to the left child - pointer to the right child
Create a Node to represent a binary tree
class Node:
def __init__(self,value):
self.left=None
self.right=None
self.value=valueWhen creating any node in tree initially left and the right pointer can be should be None.
#Create Root Node 1
n1=Node(1)
#Create Node 2
n2=Node(2)
#Create Node 3
n3=Node(3)
#Add 2 node to the left side of root node
n1.left=n2
#add 3 node to the right side of root node 1
n1.right=n3Full Example:
class Node:
def __init__(self,value):
self.left=None
self.right=None
self.value=value
#Create Root Node 1
n1=Node(1)
#Create Node 2
n2=Node(2)
#Create Node 3
n3=Node(3)
#Add 2 node to the left side of root node
n1.left=n2
#add 3 node to the right side of root node 1
n1.right=n3There are three ways of traversing a binary tree
- pre-order, - in-order, - post-order.
- First Visit Root node and print It.
- Traverse left subtree
- Traverse Right subtree
def Preorder(self,root):
if root:
print(root.value)
self.Preorder(root.left)
self.Preorder(root.right)- Traverse left subtree
- Visit the Root node and print It.
- Traverse Right subtree
def Inorder(self,root):
if root:
self.Inorder(root.left)
print(root.value)
self.Inorder(root.right)- Traverse left subtree
- Traverse Right subtree
- Visit the Root node and print It.
def Postorder(self,root):
if root:
self.Postorder(root.left)
self.Postorder(root.right)
print(root.value)Full Example:
class Node:
def __init__(self,value):
self.left=None
self.right=None
self.value=value
class Tree:
def __init__(self):
self.root=None
def Preorder(self,root):
if root:
print(root.value)
self.Preorder(root.left)
self.Preorder(root.right)
def Inorder(self,root):
if root:
self.Inorder(root.left)
print(root.value)
self.Inorder(root.right)
def Postorder(self,root):
if root:
self.Postorder(root.left)
self.Postorder(root.right)
print(root.value)
#Create Root Node
root = Node(1)
root.left= Node(2)
root.right= Node(3)
root.left.left= Node(4)
#Create Object of Simple Tree
t1=Tree()
#preorder Traversal
print("Preorder")
t1.Preorder(root)
#Inorder Traversal
print("Inorder")
t1.Inorder(root)
#Postorder Traversal
print("Postorder")
t1.Postorder(root)Output:
Preorder 1 2 4 3 Inorder 4 2 1 3 Postorder 4 2 3 1