💡 Thread removal signals completion of left subtree and visiting current node.
traverse
Traversal complete, current is null
Current pointer is now null, indicating traversal is finished. The result contains the inorder sequence.
💡 Traversal ends when there are no more nodes to visit.
Line:while current:
...
return result
💡 The algorithm successfully visited all nodes in inorder without recursion or stack.
return
Return the final inorder traversal result
The algorithm returns the result list containing the inorder traversal sequence [1, 3, 2].
💡 Returning the result completes the traversal process and provides the output.
Line:return result
💡 The final output confirms the correctness of the Morris inorder traversal.
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 = [] # STEP 1
current = root # STEP 1
while current: # STEP 2
if not current.left: # STEP 2
result.append(current.val) # STEP 3,7
current = current.right # STEP 3,7
else:
predecessor = current.left # STEP 4
while predecessor.right and predecessor.right != current: # STEP 5
predecessor = predecessor.right # STEP 5
if not predecessor.right: # STEP 5
predecessor.right = current # STEP 6
current = current.left # STEP 6
else:
predecessor.right = None # STEP 8
result.append(current.val) # STEP 8
current = current.right # STEP 8
return result # STEP 9
if __name__ == '__main__':
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(inorderTraversal(root)) # Expected output: [1,3,2]
📊
Binary Tree Inorder Traversal - Watch the Algorithm Execute, Step by Step
Watching each step shows how the algorithm cleverly creates and removes threads to traverse the tree in order without extra space.
Step 1/10
·Active fill★Answer cell
Current node: 1
123
Current node: 1
123
Current node: 2
123
Result: [1]
Current node: 2
123
DFS Stack
2 (entered)predecessor=3
Result: [1]
Current node: 2
123
DFS Stack
2 (left_done)predecessor=3
Result: [1]
Current node: 3
123
DFS Stack
2 (left_done)predecessor=3
Result: [1]
Current node: 2
123
DFS Stack
2 (left_done)predecessor=3
Result: [1, 3]
123
Result: [1, 3, 2]
123
Result: [1, 3, 2]
123
Result: [1, 3, 2]
Return: [1,3,2]
Key Takeaways
✓ Morris traversal uses temporary threads to traverse the tree without recursion or stack.
This insight is hard to see from code alone because the thread creation and removal are subtle and happen dynamically.
✓ Nodes without left children are visited immediately, simplifying traversal steps.
Understanding this helps learners see why some nodes are visited right away and others require threading.
✓ Thread removal signals completion of left subtree traversal and triggers visiting the current node.
This concrete example clarifies the key decision point where traversal switches from left subtree to root.
Practice
(1/5)
1. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
easy
A. 2
B. 0
C. 3
D. 1
Solution
Step 1: Trace dfs on leaf nodes 1 and 2
Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.
Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here
Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.
Final Answer:
Option D -> Option D
Quick Check:
One camera at root covers all nodes [OK]
Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]
Common Mistakes:
Counting cameras on leaves instead of parent
Forgetting to add camera at root if uncovered
Misinterpreting coverage states
2. You need to output all nodes of a binary tree such that each node is processed only after its left and right children have been processed. Which traversal approach guarantees this order?
easy
A. Postorder traversal using depth-first search
B. Preorder traversal using recursion
C. Level-order traversal using a queue
D. Inorder traversal using recursion
Solution
Step 1: Understand traversal order requirements
Postorder traversal processes left subtree, then right subtree, then the node itself, ensuring children are processed before the parent.
Step 2: Compare with other traversals
Preorder and inorder do not guarantee children processed before parent; level-order processes nodes by depth, not child-first.
Final Answer:
Option A -> Option A
Quick Check:
Postorder traversal matches the problem's processing order [OK]
Hint: Postorder processes children before parent [OK]
Common Mistakes:
Confusing inorder with postorder
Thinking preorder processes children first
3. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree:
1
/ \
2 3
/
4
What is the final return value of countNodes(root)?
easy
A. 4
B. 3
C. 5
D. 6
Solution
Step 1: Calculate tree height
Height h = 3 (nodes 1 -> 2 -> 4).
Step 2: Binary search on last level nodes
Last level has indices 0 to 3. Check existence:
- idx=0 exists (node 4)
- idx=1 does not exist
So left ends at 1.
Final Answer:
Option A -> Option A
Quick Check:
Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]
Hint: Count = perfect nodes + last level nodes found [OK]
Common Mistakes:
Off-by-one in binary search bounds
Miscounting last level nodes
4. You are given a binary tree and asked to transform it into a singly linked list in-place such that the linked list follows the preorder traversal of the tree. Which approach guarantees an optimal solution with O(n) time and O(h) space complexity, where h is the tree height?
easy
A. Use a reverse preorder traversal (right subtree first, then left) with a global pointer to rewire nodes in-place.
B. Perform a preorder traversal, store nodes in a list, then rebuild the linked list from the list.
C. Use a bottom-up postorder traversal to reconstruct the linked list from leaves to root.
D. Apply a greedy approach that always attaches the left subtree to the rightmost node of the right subtree.
Solution
Step 1: Understand traversal order needed
The linked list must follow preorder traversal (root, left, right).
Step 2: Identify approach that rewires in-place efficiently
Reverse preorder traversal (right, left) with a global pointer allows rewiring nodes in-place without extra storage, achieving O(n) time and O(h) space due to recursion stack.
Final Answer:
Option A -> Option A
Quick Check:
Reverse preorder traversal with global pointer rewires nodes in correct order [OK]
Hint: Reverse preorder traversal with global pointer is optimal [OK]
Common Mistakes:
Using extra space to store nodes before rebuilding
Confusing traversal order causing incorrect linked list
Trying greedy rewiring without correct traversal order
5. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?
medium
A. Line creating root node with postorder[-1]
B. Line initializing inorder_index to 0
C. Line attaching node as right child
D. Line popping from stack inside while loop
Solution
Step 1: Identify inorder_index initialization
inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.
Step 2: Consequences of wrong initialization
Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.
Final Answer:
Option B -> Option B
Quick Check:
Correct inorder_index initialization is critical for stack popping logic [OK]
Hint: inorder_index must start at last index, not zero [OK]
Common Mistakes:
Wrong inorder_index initialization
Confusing postorder traversal direction
Incorrect stack popping conditions
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.