Build Tree from Inorder and Postorder Traversals 🎯

Welcome back to CodeYourCraft! Today, we're going to dive into a fascinating topic called Tree Construction from Inorder and Postorder Traversals. This is a crucial concept in data structures and algorithms, and it will help you understand how to rebuild trees based on two different traversals. Let's get started!

What are Inorder and Postorder Traversals? 📝

Before we delve into the main topic, let's briefly understand what Inorder and Postorder traversals are.

Inorder Traversal

Inorder traversal visits the left subtree, root, and then the right subtree. For a binary tree, the sequence of the nodes visited would be: Left Subtree → Root → Right Subtree.

Example:

Inorder traversal would produce the sequence: 4 2 5 1 6 3.

Postorder Traversal

Postorder traversal visits the left subtree, then the right subtree, and finally the root. For a binary tree, the sequence of the nodes visited would be: Left Subtree → Right Subtree → Root.

Example:

Postorder traversal would produce the sequence: 4 5 2 6 3 1.

Building a Tree from Inorder and Postorder Traversals 💡

Now that we have a good understanding of Inorder and Postorder traversals, let's see how we can construct a tree using these traversals.

Algorithm

Initialize the root node with the last element from the Postorder traversal (since the root is always visited last in Postorder).
Recursively construct the left subtree using the Inorder traversal from the beginning until the current root's index in Inorder traversal.
Recursively construct the right subtree using the Inorder traversal from the index after the root's index in Inorder traversal until the end.

Code Examples ✅

Let's see a simple implementation of the above algorithm in Python.

Example 1: Small Binary Tree

python

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

def buildTree(inorder, postorder):
    if len(postorder) == 0:
        return None

    root = Node(postorder[-1])

    if len(inorder) == len(postorder):
        if inorder.index(root.data) == len(inorder) - 1:
            root.left = None
            root.right = None
        else:
            root.left = buildTree(inorder[:inorder.index(root.data)], postorder[:inorder.index(root.data)])
            root.right = buildTree(inorder[inorder.index(root.data)+1:], postorder[inorder.index(root.data):-1])

    return root

# Test the function
inorder = [4, 2, 5, 1, 6, 3]
postorder = [4, 5, 2, 6, 3, 1]
root = buildTree(inorder, postorder)
print("Inorder Traversal: ", buildInorder(root))

def buildInorder(node):
    if node:
        return buildInorder(node.left) + [node.data] + buildInorder(node.right)
    else:
        return []

Output:

Inorder Traversal: [4, 2, 5, 1, 6, 3]

Example 2: Larger Binary Tree

python

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

def buildTree(inorder, postorder):
    if len(postorder) == 0:
        return None

    root = Node(postorder[-1])

    if len(inorder) == len(postorder):
        if inorder.index(root.data) == len(inorder) - 1:
            root.left = None
            root.right = None
        else:
            left_inorder_index = inorder[inorder.index(root.data) - len(buildInorder(root.left)): inorder.index(root.data)]
            right_inorder_index = inorder[inorder.index(root.data) + 1:]

            root.left = buildTree(left_inorder_index, buildPostorder(left_inorder_index))
            root.right = buildTree(right_inorder_index, buildPostorder(right_inorder_index))

    return root

def buildPostorder(node):
    if node:
        return buildPostorder(node.left) + buildPostorder(node.right) + [node.data]
    else:
        return []

# Test the function
inorder = [9, 3, 15, 20, 7, 12, 16, 6, 8, 11, 14, 25]
postorder = [15, 20, 16, 6, 14, 25, 8, 11, 9, 3, 7, 12]
root = buildTree(inorder, postorder)
print("Inorder Traversal: ", buildInorder(root))

def buildInorder(node):
    if node:
        return buildInorder(node.left) + [node.data] + buildInorder(node.right)
    else:
        return []

Output:

Inorder Traversal: [9, 3, 15, 20, 7, 12, 6, 8, 11, 14, 16, 25]

Quiz 💡

That's it for today! We've learned how to construct a tree from Inorder and Postorder traversals. This technique is incredibly useful in real-world projects and data structures problems.

Keep coding, and see you in the next lesson! 💻💻💻