BinaryTree.md

Binary Tree

• 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)

Binary Tree Parts

- value
- pointer to the left child
- pointer to the right child

Building Binary Tree

Create a Node to represent a binary tree

class Node:
  def __init__(self,value):
    self.left=None
    self.right=None
    self.value=value

When 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=n3

Full 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=n3

Tree Traversal

There are three ways of traversing a binary tree

- pre-order, 
- in-order,
- post-order.

Pre-Order Traversal

• 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)

In-Order Traversal

• 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)

Post-Order Traversal

• 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