Tree Construction from Traversals

# Example:
# Preorder: [1, 2, 4, 5, 3, 6]
# Inorder: [4, 2, 5, 1, 6, 3]

# Step 1: Preorder ka pehla element = root = 1
# Step 2: Inorder mein 1 dhundho ✓ index 3
# Left subtree inorder: [4, 2, 5] (index 0-2)
# Right subtree inorder: [6, 3] (index 4-5)
# Step 3: Preorder mein next elements split karo
# Left subtree preorder: [2, 4, 5] (1 ke baad 3 elements)
# Right subtree preorder: [3, 6] (baaki elements)
# Step 4: Recursively dono subtrees build karo

def buildTree(preorder, inorder):
 if not preorder:
 return None
 
 root = Node(preorder[0])
 mid = inorder.index(root.val)
 
 root.left = buildTree(preorder[1:mid+1], inorder[:mid])
 root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
 
 return root

# Time: O(n�) � index search O(n) hai, n nodes
# Space: O(n) � recursion stack + new arrays

# Example:
# Postorder: [4, 5, 2, 6, 3, 1]
# Inorder: [4, 2, 5, 1, 6, 3]

# Step 1: Postorder ka last element = root = 1
# Step 2: Inorder mein 1 dhundho ✓ index 3
# Left subtree inorder: [4, 2, 5]
# Right subtree inorder: [6, 3]
# Step 3: Postorder mein left subtree ke 3 elements pehle aate hain
# Left subtree postorder: [4, 5, 2]
# Right subtree postorder: [6, 3]
# Step 4: Recursively build karo

def buildTreePost(postorder, inorder):
 if not postorder:
 return None
 
 root = Node(postorder[-1])
 mid = inorder.index(root.val)
 
 root.left = buildTreePost(postorder[:mid], inorder[:mid])
 root.right = buildTreePost(postorder[mid:-1], inorder[mid+1:])
 
 return root

# Level order: [1, 2, 3, 4, 5, 6]
# Tree:
# 1
# / \
# 2 3
# / \ / \
# 4 5 6

from collections import deque

def buildTreeLevel(levelorder):
 if not levelorder:
 return None
 
 root = Node(levelorder[0])
 queue = deque([root])
 i = 1
 
 while queue and i < len(levelorder):
 node = queue.popleft()
 
 if i < len(levelorder):
 node.left = Node(levelorder[i])
 queue.append(node.left)
 i += 1
 
 if i < len(levelorder):
 node.right = Node(levelorder[i])
 queue.append(node.right)
 i += 1
 
 return root