Write functions to implement recursive versions of preorder, inorder and postorder traversals of binary trees. Use stack to implement the recursion.

Sure, let's start by understanding what these tree traversals are:

• Preorder Traversal: Visit the root first, then traverse the left subtree, and finally the right subtree.
• Inorder Traversal: Traverse the left subtree first, then visit the root, and finally the right subtree.
• Postorder Traversal: Traverse the left subtree first, then the right subtree, and finally visit the root.

Now, let's write the functions for these traversals using recursion and stack.

First, let's define the structure of a node in the binary tree:

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

Now, let's write the functions for the traversals:

1. Preorder Traversal:

def preorder(root):
    if root:
        # Stack to keep nodes
        stack = []
        stack.append(root)

        while stack:
            node = stack.pop()
            print(node.val, end=" ")

            # Push right and left children of the popped node to stack
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

1. Inorder Traversal:

def inorder(root):
    # Set current to root of binary tree
    current = root 
    stack = [] # Initialize stack

    while True: 
        # Reach the left most Node of the current Node 
        if current is not None: 
            # Place pointer to a tree node on the stack before traversing the node's left subtree 
            stack.append(current) 
            current = current.left 
        # BackTrack from the empty subtree and visit the node at the top of the stack; however, if the stack is empty, you are done 
        elif(stack): 
            current = stack.pop() 
            print(current.val, end=" ") # Python 3 printing 
            # We have visited the node and its left subtree. Now, it's right subtree's turn 
            current = current.right  
        else: 
            break

1. Postorder Traversal:

def postorder(root):
    if root is None:
        return

    stack1 = []
    stack2 = []

    # Push root to first stack
    stack1.append(root)

    # Run while first stack is not empty
    while stack1:

        # Pop an item from stack1 and push it to stack2
        node = stack1.pop()
        stack2.append(node)

        # Push left and right children of popped item to stack1
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)

    # Print all elements of second stack
    while stack2:
        node = stack2.pop()
        print(node.val, end=" ")

In these functions, we are using a stack to keep track of nodes. In the case of preorder traversal, we first visit the root, then its left subtree and finally its right subtree. For inorder traversal, we first visit the left subtree, then the root and finally the right subtree. For postorder traversal, we first visit the left subtree, then the right subtree and finally the root.

The time complexity for these functions is O(n), where n is the number of nodes in the tree, because we are visiting each node once. The space complexity is also O(n), because in the worst case, we might have to hold all nodes in the stack.