Binary Tree:
============
==> Tree represents the nodes connected by edges.
==> non-linear data structure.
==> properties:
	1) one node among all must be a root.
	2) each node except root node must be associated with parent node.
	3) each node should contains two arbitrary number of child nodes (2).

# Binary tree

Creation of node as root:
=========================
class Node:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data

    def printTree(self):
        print(self.data)
        print(self.left)
        print(self.right)

root = Node(1993)
root.left = 2005
root.right = 2013

root.printTree()

==========================================

Inserting into Tree:
====================

# Inserting to tree

class Node:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data    # 100

    def insert(self,data):
        # comparing the new value with parent 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

    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data),
        if self.right:
            self.right.printTree()


root = Node(112)    # parent data
root.insert(102)    # 102 < 112 ==> True ==> left = 102
root.insert(144)    # 144 > 112  ==> True ==> right = 144
root.insert(97)     # 112 replace with 97

root.printTree()

======================================================
Traversing on Tree:
===================
three ways:
	1) in-order Traversal ==> left, root and right
	================================================
# Inorder Traversal

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

    def insert(self,data):
        # comparing the new value with parent 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

    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data),
        if self.right:
            self.right.printTree()

    # Inorder Traversal
    # left ==> root ==> right
    def inorderTraversal(self, root):
        res = []
        if root:
            res = self.inorderTraversal(root.left)
            res.append(root.data)
            res = res + self.inorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)

result = root.inorderTraversal(root)

print(result)
=============================================

	2) pre-order Traversal ==> root , left, right
================================================================

# Pre-order traversal

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

    def insert(self,data):
        # comparing the new value with parent 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

    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data),
        if self.right:
            self.right.printTree()

    # pre-order traversal
    # root ==> left ==> right

    def preorderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)   # root visiting
            res = res + self.preorderTraversal(root.left)   # left visiting
            res = res + self.preorderTraversal(root.right)  # right visiting
        return res

root = Node(14) # root
root.insert(27) # right
root.insert(10) # left
root.insert(35) # right
root.insert(19) # right
root.insert(42)
root.insert(31)

print(root.preorderTraversal(root))

==================================================================
	3) Post-order Traversal ==> left ==> right ==> root

# Post Order Traversal

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

    def insert(self,data):
        # comparing the new value with parent 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

    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data),
        if self.right:
            self.right.printTree()

    # post order Traversal
    # left ==> right ==> root

    def postOrderTraversal(self,root):
        res = []
        if root:
            res = res + self.postOrderTraversal(root.left)    # left visiting
            res = res + self.postOrderTraversal(root.right)   # right visiting
            res.append(root.data)   # root visiting
        return res

root = Node(27) # root
root.insert(14) # left
root.insert(35) # right
root.insert(10) # left
root.insert(19) # right
root.insert(31) # left
root.insert(42) # right

print(root.postOrderTraversal(root))