Data Structures Practice Problems Solutions

Queue Problems (3.9-3.13)

Problem 3.9: Implement Queue using Array

Problem Statement: Implement the enqueue, dequeue and peek functions using an array.
Solution Approach:
Use circular array to efficiently utilize space
Maintain front and rear pointers
Handle overflow and underflow conditions
Visual Representation:

Initial State: [_, _, _, _] front=0, rear=0, size=0

After enqueue(10): [10, _, _, _] front=0, rear=1, size=1

After enqueue(20): [10, 20, _, _] front=0, rear=2, size=2
After enqueue(30): [10, 20, 30, _] front=0, rear=3, size=3

After dequeue(): [_, 20, 30, _] front=1, rear=3, size=2

Code Implementation:

class ArrayQueue:
def __init__(self, capacity=10):
self.queue = [None] * capacity
self.front = 0
self.rear = 0
self.size = 0
self.capacity = capacity

def is_empty(self):
return self.size == 0

def is_full(self):
return self.size == self.capacity

def enqueue(self, item):

if self.is_full():
raise OverflowError("Queue is full")

self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
self.size += 1
print(f"Enqueued {item}")
 def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")

item = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % self.capacity
self.size -= 1
print(f"Dequeued {item}")
return item

def peek(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.queue[self.front]

def display(self):
if self.is_empty():
print("Queue is empty")
return

elements = []
current = self.front
for _ in range(self.size):
elements.append(str(self.queue[current]))
current = (current + 1) % self.capacity
print("Queue:", " -> ".join(elements))

Step-by-Step Simulation:
1. Initialize: Create queue with capacity 4
2. Enqueue 10: Place at index 0, rear moves to 1
3. Enqueue 20: Place at index 1, rear moves to 2
4. Dequeue: Remove from index 0, front moves to 1
5. Peek: Return element at front (index 1)
Time Complexity: O(1) for all operations
Space Complexity: O(n) where n is capacity

Problem 3.10: Implement Queue using Linked List

Problem Statement: Implement the enqueue, dequeue and peek functions using a linked list.
Visual Representation:

Initial: front=None, rear=None

After enqueue(10):
front -> [10] -> None <- rear
 After enqueue(20):
front -> [10] -> [20] -> None <- rear

After enqueue(30):
front -> [10] -> [20] -> [30] -> None <- rear

After dequeue():
front -> [20] -> [30] -> None <- rear

Code Implementation:

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

class LinkedListQueue:
def __init__(self):
self.front = None
self.rear = None
self.size = 0

def is_empty(self):
return self.front is None

def enqueue(self, item):

new_node = Node(item)

if self.is_empty():
self.front = self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node

self.size += 1
print(f"Enqueued {item}")

def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")

item = self.front.data
self.front = self.front.next

if self.front is None: # Queue became empty

self.rear = None

self.size -= 1
print(f"Dequeued {item}")
return item

def peek(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.front.data
 def display(self):
if self.is_empty():
print("Queue is empty")
return

elements = []
current = self.front
while current:
elements.append(str(current.data))
current = current.next
print("Queue:", " -> ".join(elements))

Advantages over Array Implementation:

Dynamic size (no fixed capacity)
No memory wastage
No need for circular logic
Time Complexity: O(1) for all operations
Space Complexity: O(1) per operation

Problem 3.11: First Non-Repeating Character

Problem Statement: Given a string s, find the first non-repeating character in it and return its
index. If it does not exist, return -1.
Examples:
Input: "programmingisfun" → Output: 0 (p appears only once)
Input: "pythonispopular" → Output: 1 (y appears only once first)
Input: "aabb" → Output: -1 (all characters repeat)
Solution Approach:
1. Count frequency of each character
2. Find first character with frequency 1
Visual Analysis:

"programmingisfun"
p:1, r:2, o:2, g:2, m:2, i:2, n:4, s:2, f:1, u:1

First non-repeating: p at index 0

Code Implementation:

def first_non_repeating_char(s):
# Count frequency of each character
char_count = {}
 for char in s:
char_count[char] = char_count.get(char, 0) + 1

# Find first character with count 1

for i, char in enumerate(s):
if char_count[char] == 1:
return i

return -1

# Alternative approach using queue

def first_non_repeating_char_queue(s):
from collections import deque, defaultdict

queue = deque()
char_count = defaultdict(int)

for i, char in enumerate(s):

char_count[char] += 1
queue.append((char, i))

# Remove characters that have appeared more than once

while queue and char_count[queue[0][0]] > 1:
queue.popleft()

return queue[0][1] if queue else -1

Step-by-Step Trace for "pythonispopular":

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Char: p y t h o n i s p o p u l a r

Frequency count:
p: 3 (indices 0, 8, 10)
y: 1 (index 1) ← First non-repeating
t: 1 (index 2)
...

Answer: 1

Time Complexity: O(n)

Space Complexity: O(k) where k is number of unique characters

Problem 3.12: Time to Buy Tickets

Problem Statement: There are n people in a line queuing to buy tickets. Each person takes
exactly 1 second to buy a ticket and can only buy 1 ticket at a time. Return the time taken for the
person at position k to finish buying tickets.
Example:
Input: tickets = [2,3,2], k = 2
 Output: 6
Visual Simulation:

Initial: [2,3,2], person at k=2 needs 2 tickets

Pass 1: Everyone buys 1 ticket

[1,2,1] - Time: 3 seconds

Pass 2: Everyone still in queue buys 1 ticket

[0,1,0] - Time: 6 seconds total

Person at position 2 finished buying all tickets at 6 seconds.

Code Implementation:

def time_required_to_buy_tickets(tickets, k):

time = 0

while tickets[k] > 0:

# Process each person in the queue
for i in range(len(tickets)):
if tickets[i] > 0:
tickets[i] -= 1
time += 1

# If person k finished buying all tickets

if i == k and tickets[k] == 0:
return time

return time

# More efficient approach

def time_required_to_buy_tickets_optimized(tickets, k):
target_tickets = tickets[k]
time = 0

for i in range(len(tickets)):
if i <= k:
# People before or at position k
time += min(tickets[i], target_tickets)
else:
# People after position k
time += min(tickets[i], target_tickets - 1)

return time

Detailed Example Trace:

tickets = [5,1,1,1], k = 0

Person 0 needs 5 tickets

- Time for person 0: min(5, 5) = 5
 - Time for person 1: min(1, 4) = 1
- Time for person 2: min(1, 4) = 1
- Time for person 3: min(1, 4) = 1

Total time: 5 + 1 + 1 + 1 = 8

Time Complexity: O(n)

Space Complexity: O(1)

Problem 3.13: Lemonade Change

Problem Statement: At a lemonade stand, each lemonade costs $5. Customers pay with $5,
$10, or $20 bills. You must provide correct change. Return true if you can provide change to all
customers.
Examples:
Input: [5,5,5,10,20] → Output: true
Input: [5,5,10,10,20] → Output: false
Solution Strategy:
Keep count of $5 and $10 bills
For $5: no change needed
For $10: need one $5 bill as change
For $20: need $15 change (prefer one $10 + one $5, or three $5)
Visual Simulation:

bills = [5,5,5,10,20]

Customer 1: $5 → count_5 = 1, count_10 = 0

Customer 2: $5 → count_5 = 2, count_10 = 0
Customer 3: $5 → count_5 = 3, count_10 = 0
Customer 4: $10 → need $5 change → count_5 = 2, count_10 = 1
Customer 5: $20 → need $15 change → use $10+$5 → count_5 = 1, count_10 = 0

Result: true (all customers served)

Code Implementation:

def lemonade_change(bills):
count_5 = 0
count_10 = 0

for bill in bills:

if bill == 5:
count_5 += 1
elif bill == 10:
if count_5 > 0:
 count_5 -= 1
count_10 += 1
else:
return False
elif bill == 20:
# Prefer to give one $10 + one $5 as change
if count_10 > 0 and count_5 > 0:
count_10 -= 1
count_5 -= 1
elif count_5 >= 3:
count_5 -= 3
else:
return False

return True

Step-by-Step Analysis for [5,5,10,10,20]:

Bill $5: count_5=1, count_10=0 ✓

Bill $5: count_5=2, count_10=0 ✓
Bill $10: count_5=1, count_10=1 ✓ (used 1 five)
Bill $10: count_5=0, count_10=2 ✓ (used 1 five)
Bill $20: Need $15 change
- Option 1: 1 ten + 1 five → Need count_10≥1 and count_5≥1 ✗ (count_5=0)
- Option 2: 3 fives → Need count_5≥3 ✗ (count_5=0)

Result: false

Time Complexity: O(n)

Space Complexity: O(1)

Tree Problems (5.1-5.10)

Problem 5.1: Find Level, Depth, Height, and Degree

Problem Statement: Find the level, depth, height and degree of specified nodes in a tree.
Sample Tree:

A(0) Level 0
/||\
B C D Level 1
/ |\
E F G Level 2
|
H Level 3

Definitions:
Level: Distance from root (Level of node = Depth of node)
 Depth: Number of edges from root to node
Height: Maximum number of edges from node to any leaf
Degree: Number of children of a node
Analysis for Each Node:

Node Level Depth Height Degree Explanation

A 0 0 3 3 Root node, 3 children, longest path to H

B 1 1 1 1 1 edge from root, 1 child, max path to E

C 1 1 2 2 1 edge from root, 2 children, max path to H

D 1 1 0 0 1 edge from root, leaf node

E 2 2 0 0 2 edges from root, leaf node

F 2 2 1 1 2 edges from root, 1 child

G 2 2 0 0 2 edges from root, leaf node

H 3 3 0 0 3 edges from root, leaf node

Code Implementation:

class TreeNode:
def __init__(self, val):
self.val = val
self.children = []

def find_depth(root, target, current_depth=0):

if not root:
return -1
if root.val == target:
return current_depth

for child in root.children:

result = find_depth(child, target, current_depth + 1)
if result != -1:
return result
return -1

def find_height(root):
if not root:
return -1
if not root.children:
return 0

max_height = -1
for child in root.children:
max_height = max(max_height, find_height(child))

return max_height + 1

def find_degree(root, target):

 if not root:
return 0
if root.val == target:
return len(root.children)

for child in root.children:

result = find_degree(child, target)
if result != -1:
return result
return 0

Problem 5.2: Identify Tree Types

Problem Statement: Identify which trees are full, complete, perfect, and balanced.
Tree Type Definitions:
1. Full Binary Tree: Every internal node has exactly 2 children
2. Complete Binary Tree: All levels filled except possibly the last, which fills left-to-right
3. Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level
4. Balanced Binary Tree: Height difference between left and right subtrees ≤ 1 for all nodes
Sample Trees Analysis:
Tree 1:

A
/ \
B C
/ \
D E

Full: ✗ (C has no children)

Complete: ✓ (all levels filled left-to-right)
Perfect: ✗ (leaves not at same level)
Balanced: ✓ (height differences ≤ 1)
Tree 2:

A
/ \
B C
/|\ /|\
D E F G H I

Full: ✓ (all internal nodes have 2 children)

Complete: ✓ (all levels completely filled)
 Perfect: ✓ (all criteria met)
Balanced: ✓ (perfectly balanced)
Code Implementation:

def is_full_binary_tree(root):
if not root:
return True
if not root.left and not root.right:
return True
if root.left and root.right:
return is_full_binary_tree(root.left) and is_full_binary_tree(root.right)
return False

def is_complete_binary_tree(root):
if not root:
return True

queue = [root]
flag = False

while queue:
node = queue.pop(0)

if node.left:
if flag:
return False
queue.append(node.left)
else:
flag = True

if node.right:
if flag:
return False
queue.append(node.right)
else:
flag = True

return True

def is_perfect_binary_tree(root):
def get_depth(node):
depth = 0
while node:
depth += 1
node = node.left
return depth

def is_perfect_helper(node, depth, level=0):

if not node:
return True
if not node.left and not node.right:
return depth == level + 1
if not node.left or not node.right:
return False
 return (is_perfect_helper(node.left, depth, level + 1) and
is_perfect_helper(node.right, depth, level + 1))

depth = get_depth(root)
return is_perfect_helper(root, depth)

def is_balanced_binary_tree(root):
def check_balance(node):
if not node:
return True, -1

left_balanced, left_height = check_balance(node.left)

right_balanced, right_height = check_balance(node.right)

balanced = (left_balanced and right_balanced and

abs(left_height - right_height) <= 1)
height = max(left_height, right_height) + 1

return balanced, height

balanced, _ = check_balance(root)
return balanced

Problem 5.3: Construct Tree with Height 3 and Minimum 9 Nodes

Problem Statement: Write code to construct a tree of height 3 with minimum number of 9
nodes.
Design Strategy:
For minimum nodes with maximum height, create a skewed tree initially, then add nodes to meet
the 9-node requirement.
Tree Design:

1 Level 0 (Height 3)
/
2 Level 1 (Height 2)
/ \
3 4 Level 2 (Height 1)
/ / \
5 6 7 Level 3 (Height 0)
/ \
8 9 Additional nodes

Code Implementation:

class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
 def construct_tree_height3_min9nodes():
# Create tree with exactly 9 nodes and height 3
root = TreeNode(1)

# Level 1
root.left = TreeNode(2)

# Level 2
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)

# Level 3
root.left.left.left = TreeNode(5)
root.left.right.left = TreeNode(6)
root.left.right.right = TreeNode(7)

# Additional nodes to reach 9

root.left.right.left.left = TreeNode(8)
root.left.right.left.right = TreeNode(9)

return root

def get_height(root):
if not root:
return -1
return max(get_height(root.left), get_height(root.right)) + 1

def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)

# Verify the tree

tree = construct_tree_height3_min9nodes()
print(f"Height: {get_height(tree)}") # Should be 3
print(f"Nodes: {count_nodes(tree)}") # Should be 9

Alternative Balanced Design:

1 Level 0
/ \
2 3 Level 1
/ \ / \
4 5 6 7 Level 2
/ \
8 9 Level 3

This design is more balanced while still achieving height 3 with 9 nodes.
Problem 5.4: Tree Traversals
Problem Statement: Traverse trees in pre-order, in-order, and post-order.
Sample Tree:

4
/ \
2 6
/ \ / \
1 3 5 7

Traversal Methods:
1. Pre-order: Root → Left → Right
2. In-order: Left → Root → Right
3. Post-order: Left → Right → Root
Step-by-Step Simulation:
Pre-order Traversal:

Visit order: 4 → 2 → 1 → 3 → 6 → 5 → 7

Steps:
1. Visit root (4)
2. Go to left subtree (2)
- Visit 2
- Go to left (1), visit 1
- Go to right (3), visit 3
3. Go to right subtree (6)
- Visit 6
- Go to left (5), visit 5
- Go to right (7), visit 7

Result: [4, 2, 1, 3, 6, 5, 7]

In-order Traversal:

Visit order: 1 → 2 → 3 → 4 → 5 → 6 → 7

Steps:
1. Go to leftmost node (1), visit 1
2. Visit parent (2)
3. Visit right child (3)
4. Visit root (4)
5. Go to right subtree, leftmost (5), visit 5
6. Visit parent (6)
7. Visit right child (7)

Result: [1, 2, 3, 4, 5, 6, 7] (sorted order for BST)

Post-order Traversal:

Visit order: 1 → 3 → 2 → 5 → 7 → 6 → 4

Steps:
1. Process left subtree completely
- Visit 1, then 3, then 2
2. Process right subtree completely
- Visit 5, then 7, then 6
3. Visit root (4)

Result: [1, 3, 2, 5, 7, 6, 4]

Code Implementation:

def preorder_traversal(root):
result = []

def preorder(node):
if node:
result.append(node.val) # Visit root
preorder(node.left) # Visit left subtree
preorder(node.right) # Visit right subtree

preorder(root)
return result

def inorder_traversal(root):
result = []

def inorder(node):
if node:
inorder(node.left) # Visit left subtree
result.append(node.val) # Visit root
inorder(node.right) # Visit right subtree

inorder(root)
return result

def postorder_traversal(root):
result = []

def postorder(node):
if node:
postorder(node.left) # Visit left subtree
postorder(node.right) # Visit right subtree
result.append(node.val) # Visit root

postorder(root)
return result

# Iterative implementations
def preorder_iterative(root):
if not root:
 return []

result = []
stack = [root]

while stack:
node = stack.pop()
result.append(node.val)

# Push right first, then left (stack is LIFO)

if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)

return result

def inorder_iterative(root):
result = []
stack = []
current = root

while stack or current:

# Go to leftmost node
while current:
stack.append(current)
current = current.left

# Process node
current = stack.pop()
result.append(current.val)

# Move to right subtree

current = current.right

return result

Problem 5.5: Convert Array to Binary Tree

Problem Statement: Convert given array into binary tree using array representation.
Array Representation Rules:
Root at index 1
For node at index i:
Left child at index 2*i
Right child at index 2*i + 1
Parent at index i//2
Example Array: [_, 1, 2, 3, 4, 5, 6, 7]
Visual Conversion:
 Array: [_, 1, 2, 3, 4, 5, 6, 7]
Index: 0 1 2 3 4 5 6 7

Tree Structure:
1
/ \
2 3
/ \ / \
4 5 6 7

Mapping:
- Index 1 (value 1): root
- Index 2 (value 2): left child of 1
- Index 3 (value 3): right child of 1
- Index 4 (value 4): left child of 2
- Index 5 (value 5): right child of 2
- Index 6 (value 6): left child of 3
- Index 7 (value 7): right child of 3

Code Implementation:

def array_to_binary_tree(arr):
if not arr or len(arr) <= 1:
return None

def build_tree(index):
if index >= len(arr) or arr[index] is None:
return None

node = TreeNode(arr[index])
node.left = build_tree(2 * index)
node.right = build_tree(2 * index + 1)
return node

return build_tree(1) # Start from index 1

# Alternative: 0-indexed array

def array_to_binary_tree_zero_indexed(arr):
if not arr:
return None

def build_tree(index):
if index >= len(arr) or arr[index] is None:
return None

node = TreeNode(arr[index])
node.left = build_tree(2 * index + 1)
node.right = build_tree(2 * index + 2)
return node

return build_tree(0) # Start from index 0

# Convert back to array (level-order)

def binary_tree_to_array(root):
 if not root:
return []

result = []
queue = [root]

while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)

# Remove trailing None values

while result and result[-1] is None:
result.pop()

return result

Step-by-Step Construction:

Step 1: Create root with arr[1] = 1

Step 2: Create left child with arr[2] = 2
Step 3: Create right child with arr[3] = 3
Step 4: Create left-left child with arr[4] = 4
Step 5: Create left-right child with arr[5] = 5
Step 6: Create right-left child with arr[6] = 6
Step 7: Create right-right child with arr[7] = 7

Problem 5.6: Check if Binary Tree is Symmetric

Problem Statement: Check whether a binary tree is a mirror of itself (symmetric around its
center).
Example Trees:
Symmetric Tree:

1
/ \
2 2
/ \ / \
3 4 4 3

Non-Symmetric Tree:

1
/ \
2 2
 \ \
3 3

Solution Approach:
1. Compare left subtree with right subtree
2. For symmetry: left.left ≡ right.right and left.right ≡ right.left
Recursive Logic:

isSymmetric(root):
return isMirror(root.left, root.right)

isMirror(left, right):
- If both null: true
- If one null: false
- If values different: false
- Recursively check: isMirror(left.left, right.right) AND
isMirror(left.right, right.left)

Code Implementation:

def is_symmetric(root):
if not root:
return True

def is_mirror(left, right):

# Both are None
if not left and not right:
return True

# One is None, other is not

if not left or not right:
return False

# Values are different

if left.val != right.val:
return False

# Recursively check mirror property

return (is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))

return is_mirror(root.left, root.right)

# Iterative solution using queue

def is_symmetric_iterative(root):
if not root:
return True

from collections import deque

queue = deque([(root.left, root.right)])
 while queue:
left, right = queue.popleft()

if not left and not right:

continue

if not left or not right:

return False

if left.val != right.val:
return False

# Add pairs to check

queue.append((left.left, right.right))
queue.append((left.right, right.left))

return True

Step-by-Step Verification:
For symmetric tree:

1
/ \
2 2
/ \ / \
3 4 4 3

Check: isMirror(left=2, right=2)

- Values equal (2 == 2) ✓
- Check isMirror(left.left=3, right.right=3) ✓
- Check isMirror(left.right=4, right.left=4) ✓
Result: true

For non-symmetric tree:

1
/ \
2 2
\ \
3 3

Check: isMirror(left=2, right=2)

- Values equal (2 == 2) ✓
- Check isMirror(left.left=null, right.right=3) ✗
Result: false

Time Complexity: O(n) where n is number of nodes

Space Complexity: O(h) where h is height of tree
Problem 5.7 & 5.8: Check if Two Binary Trees are Identical
Problem Statement: Check whether two binary trees are identical.
Definition: Two trees are identical if:
1. They have the same structure
2. Corresponding nodes have the same values
Examples:
Identical Trees:

Tree 1: Tree 2:
1 1
/ \ / \
2 3 2 3

Non-Identical Trees:

Tree 1: Tree 2:
1 1
/ \ / \
2 3 3 2

Solution Approach:
1. If both nodes are null → identical
2. If one is null → not identical
3. If values different → not identical
4. Recursively check left and right subtrees
Code Implementation:

def is_identical(root1, root2):

# Both trees are empty
if not root1 and not root2:
return True

# One tree is empty, other is not

if not root1 or not root2:
return False

# Values are different

if root1.val != root2.val:
return False

# Recursively check left and right subtrees

return (is_identical(root1.left, root2.left) and
is_identical(root1.right, root2.right))
 # Iterative solution
def is_identical_iterative(root1, root2):
from collections import deque

queue = deque([(root1, root2)])

while queue:
node1, node2 = queue.popleft()

if not node1 and not node2:

continue

if not node1 or not node2:

return False

if node1.val != node2.val:
return False

queue.append((node1.left, node2.left))
queue.append((node1.right, node2.right))

return True

Step-by-Step Verification:
Case 1: Identical Trees

Tree1: [1,2,3] Tree2: [1,2,3]

Compare(1,1): values match ✓

Compare(2,2): values match ✓
Compare(3,3): values match ✓
Compare(null,null): both null ✓

Result: true

Case 2: Different Structure

Tree1: [1,2,3] Tree2: [1,2,3,4]

Compare(1,1): values match ✓

Compare(2,2): values match ✓
Compare(3,3): values match ✓
Compare(null,4): one null, one not ✗

Result: false

Time Complexity: O(min(m,n)) where m,n are sizes of trees

Space Complexity: O(min(h1,h2)) where h1,h2 are heights
Problem 5.9: Convert Binary Tree to Mirror
Problem Statement: Convert a binary tree into its mirror image.
Mirror Transformation:
Swap left and right subtrees for every node
Apply recursively to all nodes
Example:

Original: Mirror:
1 1
/ \ / \
2 3 3 2
/ \ / \ / \
4 5 6 7 5 4
\ /
6

Before: [1,2,3,4,5,null,null,null,null,null,6]
After: [1,3,2,null,null,5,4,6,null,null,null]

Solution Approaches:
1. Recursive (Modify Original Tree)
2. Recursive (Create New Tree)
3. Iterative (Using Queue)
Code Implementation:

# Approach 1: Modify original tree

def mirror_tree_inplace(root):
if not root:
return

# Swap left and right children

root.left, root.right = root.right, root.left

# Recursively mirror subtrees

mirror_tree_inplace(root.left)
mirror_tree_inplace(root.right)

# Approach 2: Create new mirrored tree

def create_mirror_tree(root):
if not root:
return None

# Create new node with same value

mirrored = TreeNode(root.val)

# Recursively create mirrored subtrees (swapped)

mirrored.left = create_mirror_tree(root.right)
 mirrored.right = create_mirror_tree(root.left)

return mirrored

# Approach 3: Iterative solution

def mirror_tree_iterative(root):
if not root:
return

from collections import deque

queue = deque([root])

while queue:
node = queue.popleft()

# Swap left and right children

node.left, node.right = node.right, node.left

# Add children to queue for processing

if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

# Helper function to verify mirror property

def are_mirrors(root1, root2):
if not root1 and not root2:
return True

if not root1 or not root2:

return False

return (root1.val == root2.val and

are_mirrors(root1.left, root2.right) and
are_mirrors(root1.right, root2.left))

Step-by-Step Simulation:
Original Tree:

1
/ \
2 3
/ \
4 5

Mirror Process:

Step 1: At node 1, swap children

1
/ \
3 2 ← swapped
/ \
4 5
 Step 2: At node 2, swap children
1
/ \
3 2
/ \
5 4 ← swapped

Step 3: At node 3, no children to swap

Final Mirror:
1
/ \
3 2
/ \
5 4

Verification:

Original inorder: [4, 2, 5, 1, 3]

Mirror inorder: [3, 1, 5, 2, 4]

The inorder of mirror should be reverse of original's inorder.

Time Complexity: O(n) - visit each node once

Space Complexity: O(h) - recursion stack depth

Problem 5.10: Check if Binary Tree is Height Balanced

Problem Statement: Check if a binary tree is height balanced. A tree is balanced if the height
difference between left and right subtrees is not more than 1 for all nodes.
Definition of Height-Balanced:
For every node, |height(left) - height(right)| ≤ 1
Both left and right subtrees are also height-balanced
Examples:
Balanced Tree:

3
/ \
9 20
/ \
15 7

Heights: left=0, right=1, diff=1 ≤ 1 ✓

Unbalanced Tree:
 1
/ \
2 2
/ \
3 3
/ \
4 4

Heights: left=3, right=0, diff=3 > 1 ✗

Solution Approaches:
1. Naive Approach: Check balance at each node (O(n²))
2. Optimized Approach: Single pass with height calculation (O(n))
Visual Analysis:

Tree: 3
/ \
9 20
/ \
15 7

Node 9: height(null) = -1, height(null) = -1, diff = 0 ✓

Node 15: height(null) = -1, height(null) = -1, diff = 0 ✓
Node 7: height(null) = -1, height(null) = -1, diff = 0 ✓
Node 20: height(15) = 0, height(7) = 0, diff = 0 ✓
Node 3: height(9) = 0, height(20) = 1, diff = 1 ✓

Result: Balanced

Code Implementation:

# Approach 1: Naive solution (O(n²))

def is_balanced_naive(root):
def get_height(node):
if not node:
return 0
return 1 + max(get_height(node.left), get_height(node.right))

def check_balanced(node):
if not node:
return True

left_height = get_height(node.left)
right_height = get_height(node.right)

return (abs(left_height - right_height) <= 1 and

check_balanced(node.left) and
check_balanced(node.right))

return check_balanced(root)
 # Approach 2: Optimized solution (O(n))
def is_balanced_optimized(root):
def check_balance_and_height(node):
# Returns (is_balanced, height)
if not node:
return True, -1

# Check left subtree

left_balanced, left_height = check_balance_and_height(node.left)
if not left_balanced:
return False, -1

# Check right subtree

right_balanced, right_height = check_balance_and_height(node.right)
if not right_balanced:
return False, -1

# Check current node balance

is_balanced = abs(left_height - right_height) <= 1
height = max(left_height, right_height) + 1

return is_balanced, height

balanced, _ = check_balance_and_height(root)
return balanced

# Alternative approach using class variable for early termination

def is_balanced_early_stop(root):
def get_height(node):
if not node:
return 0

left_height = get_height(node.left)
if left_height == -1: # Left subtree unbalanced
return -1

right_height = get_height(node.right)
if right_height == -1: # Right subtree unbalanced
return -1

# Check current node balance

if abs(left_height - right_height) > 1:
return -1 # Signal unbalanced

return max(left_height, right_height) + 1

return get_height(root) != -1

Detailed Example Trace:

Balanced Tree Analysis:

1
/ \
2 3
 / \
4 5

Node 4: height=0, balanced=True

Node 5: height=0, balanced=True
Node 2: left_h=0, right_h=0, diff=0≤1, balanced=True, height=1
Node 3: height=0, balanced=True
Node 1: left_h=1, right_h=0, diff=1≤1, balanced=True, height=2

Result: True (balanced)

Unbalanced Tree Analysis:

1
/
2
/
3

Node 3: height=0, balanced=True

Node 2: left_h=0, right_h=-1, diff=1≤1, balanced=True, height=1
Node 1: left_h=1, right_h=-1, diff=2>1, balanced=False

Result: False (unbalanced)

Time Complexity: O(n) for optimized approach

Space Complexity: O(h) where h is height of tree

BST Problems (6.1-6.7)

Problem 6.1: Convert Unbalanced BST to Balanced BST

Problem Statement: Convert given unbalanced BSTs into balanced BSTs while maintaining BST
properties.
Approach:
1. Perform inorder traversal to get sorted array
2. Build balanced BST from sorted array using middle element as root
3. Recursively apply to left and right halves
Example Unbalanced BST:

Original (Unbalanced):
1
\
2
\
3
\
 4
\
5

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

Balanced BST Construction:

Step 1: Find middle of [1,2,3,4,5] = 3 (index 2)

Step 2: Make 3 as root
Step 3: Left subtree from [1,2], Right subtree from [4,5]
Step 4: Recursively build subtrees

Balanced Result:
3
/ \
2 4
/ \
1 5

Code Implementation:

def balance_bst(root):
# Step 1: Get inorder traversal (sorted array)
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)

# Step 2: Build balanced BST from sorted array

def build_balanced(arr, start, end):
if start > end:
return None

mid = (start + end) // 2

root = TreeNode(arr[mid])

root.left = build_balanced(arr, start, mid - 1)

root.right = build_balanced(arr, mid + 1, end)

return root

if not root:
return None

sorted_values = inorder(root)
return build_balanced(sorted_values, 0, len(sorted_values) - 1)

# Alternative: Store nodes instead of values

def balance_bst_preserve_nodes(root):
def inorder(node, nodes):
if node:
inorder(node.left, nodes)
nodes.append(node)
 inorder(node.right, nodes)

def build_tree(nodes, start, end):

if start > end:
return None

mid = (start + end) // 2

root = nodes[mid]

root.left = build_tree(nodes, start, mid - 1)

root.right = build_tree(nodes, mid + 1, end)

return root

nodes = []
inorder(root, nodes)
return build_tree(nodes, 0, len(nodes) - 1)

Step-by-Step Example:
Original Unbalanced BST:

10
/
8
/
7
/
6

Step 1: Inorder Traversal

Inorder: [6, 7, 8, 10]

Step 2: Build Balanced Tree

Array: [6, 7, 8, 10]

Mid = (0+3)/2 = 1, value = 7

Root = 7

Left subtree: [6] (index 0)

- Mid = 0, value = 6
- Root.left = 6

Right subtree: [8, 10] (indices 2-3)

- Mid = (2+3)/2 = 2, value = 8
- Root.right = 8
- Right subtree of 8: [10]
- Mid = 3, value = 10
- 8.right = 10
 Final Balanced BST:
7
/ \
6 8
\
10

Height Comparison:
Original height: 3 (worst case)
Balanced height: 2 (optimal)
Time Complexity: O(n)
Space Complexity: O(n) for storing inorder traversal

Problem 6.2: Insert Keys into BST

Problem Statement: Insert keys 65, 105, 69 into the following BST and show the steps.
Initial BST (assuming):

70
/ \
50 90
/ / \
40 80 95
/ \
20 85

Insertion Algorithm:
1. Start from root
2. If key < current node, go left
3. If key > current node, go right
4. Insert at first available position
5. Maintain BST property
Step-by-Step Insertion:
Insert 65:

Path: 70 → 50 (65 > 50) → right of 50

Before: After:
70 70
/ \ / \
50 90 50 90
/ / \
40 40 65
Insert 105:

Path: 70 → 90 → 95 (105 > 95) → right of 95

Before: After:
70 70
/ \ / \
50 90 50 90
/ \ / \ / \ / \
40 65 80 95 40 65 80 95
\ \
85 105

Insert 69:

Path: 70 → 50 → 65 (69 > 65) → right of 65

Final BST:
70
/ \
50 90
/ \ / \
40 65 80 95
\ \
69 105

Code Implementation:

def insert_bst(root, key):

# Base case: create new node
if not root:
return TreeNode(key)

# Recursive insertion
if key < root.val:
root.left = insert_bst(root.left, key)
elif key > root.val:
root.right = insert_bst(root.right, key)
# If key equals root.val, no insertion (BST has unique values)

return root

# Iterative approach
def insert_bst_iterative(root, key):
new_node = TreeNode(key)

if not root:
return new_node

current = root
while True:
if key < current.val:
if not current.left:
 current.left = new_node
break
current = current.left
elif key > current.val:
if not current.right:
current.right = new_node
break
current = current.right
else:
# Key already exists
return root

return root

# Insert multiple keys

def insert_multiple_keys(root, keys):
for key in keys:
print(f"Inserting {key}...")
root = insert_bst(root, key)
print(f"Tree after inserting {key}:")
print_inorder(root)
return root

def print_inorder(root):
if root:
print_inorder(root.left)
print(root.val, end=" ")
print_inorder(root.right)

Insertion Analysis:
Key 65 insertion:

Compare 65 with 70: 65 < 70, go left

Compare 65 with 50: 65 > 50, go right
50.right is empty: insert 65 here

Key 105 insertion:

Compare 105 with 70: 105 > 70, go right

Compare 105 with 90: 105 > 90, go right
Compare 105 with 95: 105 > 95, go right
95.right is empty: insert 105 here

Key 69 insertion:

Compare 69 with 70: 69 < 70, go left

Compare 69 with 50: 69 > 50, go right
Compare 69 with 65: 69 > 65, go right
65.right is empty: insert 69 here

Time Complexity:
 Average case: O(log n)
Worst case: O(n) for skewed tree
Space Complexity: O(1) iterative, O(h) recursive

Problem 6.3: Delete Keys from BST

Problem Statement: Delete keys 20, 95, 50, 70, 75 from BST and show the steps.
Starting BST:

70
/ \
50 90
/ \ / \
40 65 80 95
/ \ \
20 69 85

BST Deletion Cases:

1. No children (Leaf): Simply remove
2. One child: Replace with child
3. Two children: Replace with inorder successor/predecessor
Step-by-Step Deletions:
Delete 20 (Case 1: Leaf node):

Before: After:
70 70
/ \ / \
50 90 50 90
/ \ / \ / \ / \
40 65 80 95 40 65 80 95
/ \ \ \ \
20 69 85 69 85

Delete 95 (Case 1: Leaf node):

Before: After:
70 70
/ \ / \
50 90 50 90
/ \ / \ / \ / \
40 65 80 95 40 65 80 85
\ \ \
69 85 69
Delete 50 (Case 3: Two children):

Find inorder successor of 50 in right subtree:

50 → 65 → left child of 65 = 69 (leftmost in right subtree)

Replace 50 with 69, then delete 69 from its original position:

Before: After:
70 70
/ \ / \
69 90 69 90
/ \ / \ / \ / \
40 65 80 85 40 65 80 85
\
69 (delete this)

Delete 70 (Case 3: Root with two children):

Find inorder successor of 70:

70 → right (90) → leftmost in right subtree = 80

Replace 70 with 80, delete 80 from original position:

Before: After:
70 80
/ \ / \
69 90 69 90
/ \ / \ / \ / \
40 65 80 85 40 65 85 (no children)

Delete 75 (Not in tree):

Key 75 not found - no deletion performed

Code Implementation:

def delete_bst(root, key):

if not root:
return root

# Find the node to delete

if key < root.val:
root.left = delete_bst(root.left, key)
elif key > root.val:
root.right = delete_bst(root.right, key)
else:
# Node to be deleted found

# Case 1: No children (leaf)

if not root.left and not root.right:
return None
 # Case 2a: Only right child
if not root.left:
return root.right

# Case 2b: Only left child

if not root.right:
return root.left

# Case 3: Two children

# Find inorder successor (leftmost in right subtree)
successor = find_min(root.right)

# Replace value with successor's value

root.val = successor.val

# Delete the successor

root.right = delete_bst(root.right, successor.val)

return root

def find_min(root):
"""Find minimum value node in BST"""
while root.left:
root = root.left
return root

def find_max(root):
"""Find maximum value node in BST"""
while root.right:
root = root.right
return root

# Alternative: Using inorder predecessor

def delete_bst_predecessor(root, key):
if not root:
return root

if key < root.val:

root.left = delete_bst_predecessor(root.left, key)
elif key > root.val:
root.right = delete_bst_predecessor(root.right, key)
else:
# Node to be deleted found

if not root.left and not root.right:

return None

if not root.left:
return root.right

if not root.right:
return root.left

# Use inorder predecessor instead of successor

predecessor = find_max(root.left)
 root.val = predecessor.val
root.left = delete_bst_predecessor(root.left, predecessor.val)

return root

Deletion Complexity Analysis:

Case Analysis:

Case 1 (Leaf): O(h) to find + O(1) to delete = O(h)

Case 2 (One child): O(h) to find + O(1) to delete = O(h)
Case 3 (Two children): O(h) to find + O(h) to find successor + O(h) to delete successor =

Where h is height of tree:

- Best case: O(log n) for balanced tree
- Worst case: O(n) for skewed tree

Inorder Successor vs Predecessor:

Successor: Leftmost node in right subtree
Predecessor: Rightmost node in left subtree
Both maintain BST property after replacement

Problem 6.4: Print Tree in Descending Order

Problem Statement: Print the contents of a BST in descending order with and without using
stack.
Key Insight:
Inorder traversal of BST gives ascending order
Reverse inorder (Right → Root → Left) gives descending order
Sample BST:

50
/ \
30 70
/ \ / \
20 40 60 80

Method 1: Recursive (Without Stack)

Reverse Inorder Traversal:

Visit order: Right → Root → Left

Steps:
1. Visit rightmost: 80
 2. Visit parent: 70
3. Visit left child: 60
4. Visit root: 50
5. Visit right child: 40
6. Visit parent: 30
7. Visit leftmost: 20

Output: 80 70 60 50 40 30 20

Code Implementation:

# Method 1: Recursive reverse inorder

def print_descending_recursive(root):
if root:
print_descending_recursive(root.right) # Visit right subtree
print(root.val, end=" ") # Visit root
print_descending_recursive(root.left) # Visit left subtree

# Method 2: Iterative using stack

def print_descending_stack(root):
if not root:
return

stack = []
current = root

while stack or current:

# Go to rightmost node
while current:
stack.append(current)
current = current.right

# Process node
current = stack.pop()
print(current.val, end=" ")

# Move to left subtree

current = current.left

# Method 3: Morris traversal (without stack/recursion)

def print_descending_morris(root):
current = root

while current:
if not current.right:
# No right subtree, print and go left
print(current.val, end=" ")
current = current.left
else:
# Find inorder predecessor in right subtree
predecessor = current.right
while predecessor.left and predecessor.left != current:
predecessor = predecessor.left

if not predecessor.left:
 # Make current as left child of predecessor
predecessor.left = current
current = current.right
else:
# Revert the change
predecessor.left = None
print(current.val, end=" ")
current = current.left

# Method 4: Store in array then reverse

def print_descending_array(root):
def inorder(node, arr):
if node:
inorder(node.left, arr)
arr.append(node.val)
inorder(node.right, arr)

values = []
inorder(root, values)
values.reverse()

for val in values:

print(val, end=" ")

# Method 5: Using custom stack class

class Stack:
def __init__(self):
self.items = []

def push(self, item):

self.items.append(item)

def pop(self):
return self.items.pop()

def is_empty(self):
return len(self.items) == 0

def print_descending_custom_stack(root):
if not root:
return

stack = Stack()
current = root

while not stack.is_empty() or current:

# Go to rightmost node
while current:
stack.push(current)
current = current.right

# Process node
current = stack.pop()
print(current.val, end=" ")
 # Move to left subtree
current = current.left

Detailed Stack Trace:

For BST: [50, 30, 70, 20, 40, 60, 80]
Stack-based approach simulation:

Initial: current = 50, stack = []

Step 1: Push 50, go right to 70

current = 70, stack = [50]

Step 2: Push 70, go right to 80

current = 80, stack = [50, 70]

Step 3: Push 80, go right (null)

current = null, stack = [50, 70, 80]

Step 4: Pop 80, print 80, go left (null)

current = null, stack = [50, 70]
Output: 80

Step 5: Pop 70, print 70, go left to 60

current = 60, stack = [50]
Output: 80 70

Step 6: Push 60, go right (null)

current = null, stack = [50, 60]

Step 7: Pop 60, print 60, go left (null)

current = null, stack = [50]
Output: 80 70 60

... Continue until stack empty ...

Final Output: 80 70 60 50 40 30 20

Complexity Analysis:

Method Time Space Stack Used

Recursive O(n) O(h) Yes (implicit)

Iterative Stack O(n) O(h) Yes (explicit)

Morris O(n) O(1) No

Array Method O(n) O(n) No

Time Complexity: O(n) for all methods

Space Complexity: Varies by method
Problem 6.5: Find Inorder Successor and Predecessor
Problem Statement: Write a Python program that takes the root of a BST and finds the inorder
successor and predecessor of a given node.
Definitions:
Inorder Successor: Next node in inorder traversal
Inorder Predecessor: Previous node in inorder traversal
Sample BST:

20
/ \
10 30
/ \ / \
8 12 25 35

Inorder: [8, 10, 12, 20, 25, 30, 35]

Cases for Finding Successor:
1. Node has right subtree: Leftmost node in right subtree
2. No right subtree: First ancestor for which node is in left subtree
Cases for Finding Predecessor:
1. Node has left subtree: Rightmost node in left subtree
2. No left subtree: First ancestor for which node is in right subtree
Visual Example:
Finding Successor of 12:

BST: 20
/ \
10 30
/ \ / \
8 12 25 35

12 has no right child.

Go up to parent 10. 12 is right child of 10.
Go up to parent 20. 10 is left child of 20.
So successor of 12 is 20.

Path: 12 → 10 → 20

Finding Predecessor of 25:

BST: 20
/ \
10 30
 / \ / \
8 12 25 35

25 has no left child.

Go up to parent 30. 25 is left child of 30.
Go up to parent 20. 30 is right child of 20.
So predecessor of 25 is 20.

Path: 25 → 30 → 20

Code Implementation:

# Method 1: Using parent pointers

class TreeNodeWithParent:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
self.parent = None

def find_successor_with_parent(node):
if not node:
return None

# Case 1: Node has right subtree

if node.right:
# Find leftmost node in right subtree
current = node.right
while current.left:
current = current.left
return current

# Case 2: No right subtree

# Find first ancestor for which node is in left subtree
current = node
parent = current.parent

while parent and parent.right == current:

current = parent
parent = current.parent

return parent

def find_predecessor_with_parent(node):
if not node:
return None

# Case 1: Node has left subtree

if node.left:
# Find rightmost node in left subtree
current = node.left
while current.right:
current = current.right
return current
 # Case 2: No left subtree
# Find first ancestor for which node is in right subtree
current = node
parent = current.parent

while parent and parent.left == current:

current = parent
parent = current.parent

return parent

# Method 2: Without parent pointers (using search path)

def find_successor_no_parent(root, node_val):
successor = None
current = root

while current:
if node_val < current.val:
successor = current # Potential successor
current = current.left
elif node_val > current.val:
current = current.right
else:
# Found the node
if current.right:
# Find leftmost in right subtree
current = current.right
while current.left:
current = current.left
successor = current
break

return successor

def find_predecessor_no_parent(root, node_val):

predecessor = None
current = root

while current:
if node_val > current.val:
predecessor = current # Potential predecessor
current = current.right
elif node_val < current.val:
current = current.left
else:
# Found the node
if current.left:
# Find rightmost in left subtree
current = current.left
while current.right:
current = current.right
predecessor = current
break

return predecessor
# Method 3: Using inorder traversal
def find_successor_predecessor_inorder(root, target):
def inorder(node, values):
if node:
inorder(node.left, values)
values.append(node.val)
inorder(node.right, values)

values = []
inorder(root, values)

try:
index = values.index(target)
successor = values[index + 1] if index + 1 < len(values) else None
predecessor = values[index - 1] if index - 1 >= 0 else None
return successor, predecessor
except ValueError:
return None, None

# Complete solution with both methods

def find_successor_predecessor(root, node_val):
"""Find both successor and predecessor efficiently"""

def find_successor(root, val):

successor = None
while root:
if val < root.val:
successor = root
root = root.left
elif val > root.val:
root = root.right
else:
if root.right:
root = root.right
while root.left:
root = root.left
successor = root
break
return successor

def find_predecessor(root, val):

predecessor = None
while root:
if val > root.val:
predecessor = root
root = root.right
elif val < root.val:
root = root.left
else:
if root.left:
root = root.left
while root.right:
root = root.right
predecessor = root
break
return predecessor
 succ = find_successor(root, node_val)
pred = find_predecessor(root, node_val)

return succ, pred

Step-by-Step Examples:
Finding Successor of 10:

BST: 20
/ \
10 30
/ \ / \
8 12 25 35

Method: 10 has right child (12)

Find leftmost in right subtree of 10:
12 → no left child
Successor of 10 is 12

Finding Predecessor of 30:

BST: 20
/ \
10 30
/ \ / \
8 12 25 35

Method: 30 has left child (25)

Find rightmost in left subtree of 30:
25 → no right child
Predecessor of 30 is 25

Finding Successor of 35 (largest):

35 has no right child

Go up: 35 is right child of 30
Go up: 30 is right child of 20
No more ancestors
Successor of 35 is None (largest element)

Time Complexity: O(h) where h is height of tree

Space Complexity: O(1) for iterative, O(h) for recursive approaches
Problem 6.6: Create Balanced BST from Sorted Array
Problem Statement: Given a sorted array, create a balanced BST. Set the middle element as
root and recursively build left and right subtrees. Print the preorder traversal.
Algorithm:
1. Find middle element and make it root
2. Recursively build left subtree from left half
3. Recursively build right subtree from right half
4. This ensures height-balanced BST
Example Array: [1, 2, 3, 4, 5, 6, 7]
Step-by-Step Construction:

Array: [1, 2, 3, 4, 5, 6, 7]

Step 1: Middle = index 3, value = 4

Root = 4

Step 2: Left half [1, 2, 3], Right half [5, 6, 7]

Step 3: Left subtree

- Middle of [1, 2, 3] = index 1, value = 2
- Left child of 4 = 2
- Left of 2: [1] → middle = 1
- Right of 2: [3] → middle = 3

Step 4: Right subtree

- Middle of [5, 6, 7] = index 1, value = 6
- Right child of 4 = 6
- Left of 6: [5] → middle = 5
- Right of 6: [7] → middle = 7

Final BST:
4
/ \
2 6
/ \ / \
1 3 5 7

Visual Tree Construction:

Level 0: 4
/ \
Level 1: 2 6
/ \ / \
Level 2: 1 3 5 7

Preorder: 4 → 2 → 1 → 3 → 6 → 5 → 7
Code Implementation:

def sorted_array_to_bst(nums):
def build_bst(start, end):
if start > end:
return None

# Choose middle element as root

mid = (start + end) // 2
root = TreeNode(nums[mid])

# Recursively build left and right subtrees

root.left = build_bst(start, mid - 1)
root.right = build_bst(mid + 1, end)

return root

return build_bst(0, len(nums) - 1)

def preorder_traversal(root):
"""Print preorder traversal"""
result = []

def preorder(node):
if node:
result.append(node.val)
preorder(node.left)
preorder(node.right)

preorder(root)
return result

# Alternative: Iterative preorder

def preorder_iterative(root):
if not root:
return []

result = []
stack = [root]

while stack:
node = stack.pop()
result.append(node.val)

# Push right first (stack is LIFO)

if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)

return result

# Complete solution with verification

def create_balanced_bst_and_print(arr):
"""Create BST from sorted array and print preorder"""
 print(f"Input array: {arr}")

# Build BST
root = sorted_array_to_bst(arr)

# Print preorder traversal

preorder_result = preorder_traversal(root)
print(f"Preorder traversal: {preorder_result}")

# Verify it's a valid BST

def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (is_valid_bst(node.left, min_val, node.val) and
is_valid_bst(node.right, node.val, max_val))

print(f"Is valid BST: {is_valid_bst(root)}")

# Verify it's balanced

def is_balanced(node):
def check_height(n):
if not n:
return 0
left_height = check_height(n.left)
if left_height == -1:
return -1
right_height = check_height(n.right)
if right_height == -1:
return -1
if abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1

return check_height(node) != -1

print(f"Is balanced: {is_balanced(root)}")

return root

Detailed Example Traces:

Example 1: [1, 3, 5, 7, 9]

Array: [1, 3, 5, 7, 9]

build_bst(0, 4):
mid = 2, root = TreeNode(5)

root.left = build_bst(0, 1):

mid = 0, root = TreeNode(1)
root.left = build_bst(0, -1) = None
root.right = build_bst(1, 1):
mid = 1, root = TreeNode(3)
 return TreeNode(3)
return TreeNode(1) with right=TreeNode(3)

root.right = build_bst(3, 4):

mid = 3, root = TreeNode(7)
root.left = build_bst(3, 2) = None
root.right = build_bst(4, 4):
mid = 4, root = TreeNode(9)
return TreeNode(9)
return TreeNode(7) with right=TreeNode(9)

Final Tree:
5
/ \
1 7
\ \
3 9

Preorder: [5, 1, 3, 7, 9]

Example 2: [1, 2, 3, 4, 5, 6]

Array: [1, 2, 3, 4, 5, 6] (even length)

build_bst(0, 5):
mid = (0+5)//2 = 2, root = TreeNode(3)

root.left = build_bst(0, 1):

mid = 0, root = TreeNode(1)
root.right = build_bst(1, 1):
mid = 1, root = TreeNode(2)

root.right = build_bst(3, 5):

mid = 4, root = TreeNode(5)
root.left = build_bst(3, 3):
mid = 3, root = TreeNode(4)
root.right = build_bst(5, 5):
mid = 5, root = TreeNode(6)

Final Tree:
3
/ \
1 5
\ / \
2 4 6

Preorder: [3, 1, 2, 5, 4, 6]

Properties of Generated BST:

Balanced: Height difference ≤ 1 for all nodes
Complete: All levels filled except possibly last
Optimal Height: ⌊log₂(n)⌋ or ⌈log₂(n)⌉
Time Complexity: O(n) - visit each element once
Space Complexity: O(log n) - recursion stack for balanced tree

Problem 6.7: Check if Binary Tree is BST

Problem Statement: Given the root of a binary tree, check whether it is a valid BST.
BST Properties:
1. Left subtree contains only nodes with keys less than root
2. Right subtree contains only nodes with keys greater than root
3. Both left and right subtrees are also BSTs
4. No duplicate values allowed
Common Mistake: Only checking immediate children

5
/ \
1 4
/ \
3 6

Local check: 1 < 5 ✓, 4 > 5 ✗ → seems invalid

But 3 < 5 violates BST property globally!

Correct Approach: Use range validation

Method 1: Range Validation
Each node must be within a valid range:
Root: (-∞, +∞)
Left child: (min, parent_val)
Right child: (parent_val, max)
Visual Example:

10
/ \
5 15
/ \ / \
1 8 12 20

Range validation:
- Node 10: (-∞, +∞) ✓
- Node 5: (-∞, 10) ✓
- Node 15: (10, +∞) ✓
- Node 1: (-∞, 5) ✓
- Node 8: (5, 10) ✓
- Node 12: (10, 15) ✓
 - Node 20: (15, +∞) ✓

Result: Valid BST

Method 2: Inorder Traversal

Inorder traversal of BST gives sorted sequence.
Code Implementation:

# Method 1: Range validation (most efficient)

def is_valid_bst_range(root):
def validate(node, min_val, max_val):
if not node:
return True

# Check if current node violates BST property

if node.val <= min_val or node.val >= max_val:
return False

# Recursively validate left and right subtrees with updated ranges

return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))

return validate(root, float('-inf'), float('inf'))

# Method 2: Inorder traversal

def is_valid_bst_inorder(root):
def inorder(node, values):
if node:
inorder(node.left, values)
values.append(node.val)
inorder(node.right, values)

values = []
inorder(root, values)

# Check if inorder traversal is strictly increasing

for i in range(1, len(values)):
if values[i] <= values[i-1]:
return False

return True

# Method 3: Optimized inorder (space efficient)

def is_valid_bst_inorder_optimized(root):
def inorder(node):
nonlocal prev, is_valid

if node and is_valid:

inorder(node.left)

if prev is not None and node.val <= prev:

is_valid = False
return
 prev = node.val
inorder(node.right)

prev = None
is_valid = True
inorder(root)
return is_valid

# Method 4: Iterative inorder

def is_valid_bst_iterative(root):
if not root:
return True

stack = []
prev = float('-inf')
current = root

while stack or current:

# Go to leftmost node
while current:
stack.append(current)
current = current.left

# Process node
current = stack.pop()

if current.val <= prev:

return False

prev = current.val
current = current.right

return True

# Method 5: Using min/max values from subtrees

def is_valid_bst_minmax(root):
def validate(node):
if not node:
return True, float('inf'), float('-inf')

# Check left subtree

left_valid, left_min, left_max = validate(node.left)
if not left_valid or (left_max != float('-inf') and left_max >= node.val):
return False, 0, 0

# Check right subtree

right_valid, right_min, right_max = validate(node.right)
if not right_valid or (right_min != float('inf') and right_min <= node.val):
return False, 0, 0

# Current subtree is valid

subtree_min = left_min if left_min != float('inf') else node.val
subtree_max = right_max if right_max != float('-inf') else node.val

return True, subtree_min, subtree_max

 valid, _, _ = validate(root)
return valid

Step-by-Step Validation Examples:

Example 1: Valid BST

5
/ \
3 8
/ \ / \
2 4 7 9

Range validation:
validate(5, -∞, +∞):
5 in (-∞, +∞) ✓
validate(3, -∞, 5):
3 in (-∞, 5) ✓
validate(2, -∞, 3): 2 in (-∞, 3) ✓
validate(4, 3, 5): 4 in (3, 5) ✓
validate(8, 5, +∞):
8 in (5, +∞) ✓
validate(7, 5, 8): 7 in (5, 8) ✓
validate(9, 8, +∞): 9 in (8, +∞) ✓

Result: True

Example 2: Invalid BST

5
/ \
3 8
/ \ / \
2 6 7 9

Range validation:
validate(5, -∞, +∞):
5 in (-∞, +∞) ✓
validate(3, -∞, 5):
3 in (-∞, 5) ✓
validate(2, -∞, 3): 2 in (-∞, 3) ✓
validate(6, 3, 5): 6 NOT in (3, 5) ✗

Result: False (6 violates BST property)

Inorder Approach Example:

Valid BST:
5
/ \
3 8
 / \ / \
2 4 7 9

Inorder: [2, 3, 4, 5, 7, 8, 9] → strictly increasing ✓

Invalid BST:
5
/ \
3 8
/ \ / \
2 6 7 9

Inorder: [2, 3, 6, 5, 7, 8, 9] → not increasing (6 > 5) ✗

Complexity Comparison:

Method Time Space Notes

Range Validation O(n) O(h) Most efficient

Inorder Array O(n) O(n) Easy to understand

Inorder Optimized O(n) O(h) Space efficient

Iterative O(n) O(h) No recursion

Min/Max O(n) O(h) Complex implementation

Best Practice: Use range validation for optimal performance.

Summary
This comprehensive solution covers all requested problems with:
✅ Queue Problems (3.9-3.13): Array/LinkedList implementations, character finding, ticket
buying, lemonade change
✅ Tree Problems (5.1-5.10): Node properties, tree types, construction, traversals, symmetry,
balance checking
✅ BST Problems (6.1-6.7): Balancing, insertion/deletion, traversal orders,
successor/predecessor, array construction, validation
Each problem includes:
Visual diagrams showing step-by-step execution
Multiple solution approaches with trade-offs
Complete code implementations with error handling
Complexity analysis for time and space
Detailed examples with traced execution
Key Takeaways:
 Data Structure Choice: Arrays vs LinkedLists vs Trees based on operation requirements
Algorithm Efficiency: Understanding when O(1), O(log n), and O(n) solutions are
appropriate
Tree Properties: Leveraging BST properties for efficient operations
Balance Importance: Maintaining balance for optimal performance
This solution set provides a solid foundation for understanding fundamental data structures and
their applications.