Practice
inorderTraversal on this tree?Tree structure:
2
/ \ 1 3
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
result = []
current = root
while current:
if not current.left:
result.append(current.val) # visit node
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = current # create thread
current = current.left
else:
predecessor.right = None # remove thread
result.append(current.val) # visit node
current = current.right
return result
Solution
Step 1: Trace traversal starting at root=2
Current=2 has left child 1, find predecessor in left subtree: node 1 (no right child). Create thread from 1.right to 2, move current to 1.Step 2: Visit node 1 (no left child), append 1, move current to 1.right which points to 2 (thread).
Remove thread, append 2, move current to 2.right=3. Node 3 has no left child, append 3, move current to null.Final Answer:
Option A -> Option AQuick Check:
Inorder traversal of tree 1,2,3 is [1,2,3] [OK]
- Appending before removing thread
- Visiting root before left subtree
- Confusing preorder with inorder output
preorderTraversal on the tree below?
Tree structure:
1
/ \
2 3
def preorderTraversal(root):
result = []
current = root
while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
result.append(current.val)
current = current.left
else:
predecessor.right = None
current = current.right
return result
Solution
Step 1: Trace first iteration with current=1
Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.Step 2: Trace second iteration with current=2
Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).Step 3: Detect thread at 2.right=1
Since predecessor.right == current, reset 2.right=None, move current=1.right=3.Step 4: Trace current=3
Node 3 has no left child, append 3, move current=3.right=None, loop ends.Final Answer:
Option B -> Option BQuick Check:
Output matches preorder traversal [1,2,3] [OK]
- Appending nodes in wrong order
- Not resetting threaded links
- Confusing left and right child traversal
Solution
Step 1: Understand the problem constraints
Reconstructing a binary tree from preorder and inorder requires knowing root positions quickly to split subtrees.Step 2: Identify the optimal approach
Using a hash map for inorder indices allows O(1) root lookups, avoiding repeated O(n) searches in recursion.Final Answer:
Option D -> Option DQuick Check:
Hash map lookup avoids repeated scanning [OK]
- Assuming greedy or BFS can reconstruct tree correctly
- Confusing DP with tree construction
- Ignoring the need for quick root index lookup
def preorderTraversal(root):
result = []
current = root
while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
result.append(current.val)
current = current.left
else:
# Bug here
current = current.right
return result
Solution
Step 1: Identify missing restoration of tree structure
In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.Step 2: Locate missing line
The else block lacks the linepredecessor.right = None, causing the threaded link to persist.Final Answer:
Option A -> Option AQuick Check:
Without resetting, tree remains modified after traversal [OK]
- Forgetting to restore tree structure
- Appending nodes in wrong order
- Incorrect loop conditions
def deserialize(data):
if not data:
return None
vals = data.split(',')
root = TreeNode(int(vals[0]))
queue = deque([root])
i = 1
while queue:
node = queue.popleft()
if vals[i] != 'X':
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] != 'X':
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root
Solution
Step 1: Identify potential infinite loop
The loop condition 'while queue:' does not check if 'i' has exceeded vals length, risking index out of range or infinite loop.Step 2: Understand impact on deserialization
Without checking 'i < len(vals)', the loop may continue after all nodes processed, causing errors or incorrect tree structure.Final Answer:
Option D -> Option DQuick Check:
Loop condition must ensure 'i' stays within bounds to avoid deserialization bugs [OK]
- Not checking index bounds in deserialization loops
- Mixing up left and right child assignments
- Forgetting to append children to queue
