Binary Tree Inorder Traversal

📋

Problem

Imagine you have a family tree and want to list all members in a specific order that respects their generational hierarchy. Inorder traversal helps you visit nodes in a left-root-right sequence, which is essential in many tree-based algorithms.

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder traversal visits the left subtree, then the root node, and finally the right subtree.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be positive, negative, or zero.

Edge cases: Single node tree → output is the single node valueTree with only left children → output is nodes in descending orderTree with only right children → output is nodes in ascending order

</>

IDE

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:public List<Integer> inorderTraversal(TreeNode root)vector<int> inorderTraversal(TreeNode* root)function inorderTraversal(root)

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    # Write your solution here
    pass

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> inorderTraversal(TreeNode* root) {
    // Write your solution here
    return {};
}

function inorderTraversal(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2, 3]Preorder traversal implemented instead of inorder (root-left-right instead of left-root-right).✅ Change traversal order to visit left subtree first, then root, then right subtree.

Wrong: [1, 3, 2]Missed visiting left subtree of right child or incorrect recursion order.✅ Ensure recursive call visits left child before appending root value.

Wrong: [1, 2]Greedy approach visiting root before left subtree in a tree with right child only.✅ Traverse left subtree fully before root to respect inorder sequence.

Wrong: Non-terminating or timeoutInefficient traversal causing exponential time complexity or infinite recursion.✅ Implement traversal with O(n) time complexity using recursion, stack, or Morris traversal.

✓

Test Cases

Handle base cases like empty tree and single node carefully.

Focus on traversal order and avoid common traversal order mistakes.

Optimize your solution to run efficiently on large trees.

t1_01basic

Input{"root":[1,null,2,3]}

Expected[1,3,2]

⏱ Performance - must finish in 2000ms

Inorder traversal visits left subtree (none), root (1), then left subtree of 2 (3), then 2.

💡 Recall inorder traversal order: left subtree, root, right subtree.

💡 Use recursion or stack to traverse left subtree before visiting root.

💡 Append node values after traversing left subtree and before right subtree.

Why it failed: Output incorrect: likely missed visiting left subtree before root or incorrect traversal order. Fix by ensuring left subtree is fully traversed before appending root value.

✓ Correct inorder traversal order implemented.

t1_02basic

Input{"root":[4,2,5,1,3]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Inorder traversal visits left subtree (1,2,3), root (4), then right subtree (5).

💡 Traverse left subtree completely before visiting root node.

💡 Use stack or recursion to maintain traversal state.

💡 Ensure nodes are appended in left-root-right order.

Why it failed: Output incorrect: likely visited root before left subtree or skipped nodes. Fix by strictly following left-root-right order.

✓ Traversal correctly visits nodes in inorder sequence.

t2_01edge

Input{"root":null}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree returns empty list as there are no nodes to traverse.

💡 Check if root is null before traversal.

💡 Return empty list immediately if tree is empty.

💡 Avoid null pointer exceptions by handling empty input.

Why it failed: Output not empty for null root input. Fix by adding base case: if root is null, return empty list.

✓ Correctly handles empty tree input.

t2_02edge

Input{"root":[42]}

Expected[42]

⏱ Performance - must finish in 2000ms

Single node tree returns list with only that node's value.

💡 Inorder traversal of single node is just that node.

💡 Ensure traversal handles leaf nodes correctly.

💡 Return list containing single node value.

Why it failed: Output incorrect for single node tree. Fix by correctly appending root value when no children exist.

✓ Correctly returns single node value.

t2_03edge

Input{"root":[3,2,null,1]}

Expected[1,2,3]

⏱ Performance - must finish in 2000ms

Tree with only left children returns nodes in descending order (leftmost to root).

💡 Traverse left subtree fully before root.

💡 No right children to visit in this tree.

💡 Result should be sorted descending due to left-only structure.

Why it failed: Output incorrect for left-only tree. Fix by ensuring traversal visits all left descendants before root.

✓ Correctly traverses left-only tree in inorder.

t2_04edge

Input{"root":[1,null,2,null,3]}

Expected[1,2,3]

⏱ Performance - must finish in 2000ms

Tree with only right children returns nodes in ascending order (root to rightmost).

💡 Traverse root before right subtree.

💡 No left children to visit in this tree.

💡 Result should be sorted ascending due to right-only structure.

Why it failed: Output incorrect for right-only tree. Fix by ensuring traversal visits root before right descendants.

✓ Correctly traverses right-only tree in inorder.

t3_01corner

Input{"root":[5,3,7,2,4,6,8]}

Expected[2,3,4,5,6,7,8]

⏱ Performance - must finish in 2000ms

Balanced tree inorder traversal visits nodes in sorted order.

💡 Inorder traversal of BST yields sorted node values.

💡 Check that left subtree fully traversed before root and right subtree.

💡 Fix off-by-one errors in recursion or iteration to include all nodes.

Why it failed: Output incorrect due to missing nodes or wrong order. Fix by correcting traversal to include all nodes in left-root-right order.

✓ Correctly traverses balanced tree in inorder.

t3_02corner

Input{"root":[1,null,2]}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Test to catch greedy approach that visits root before left subtree incorrectly.

💡 Inorder traversal must visit left subtree before root.

💡 Greedy approach visiting root first is incorrect here.

💡 Fix traversal order to left-root-right, not root-left-right.

Why it failed: Output incorrect due to greedy root-first visit. Fix by changing traversal order to left subtree before root.

✓ Traversal order respects inorder sequence.

t3_03corner

Input{"root":[10,5,15]}

Expected[5,10,15]

⏱ Performance - must finish in 2000ms

Test to catch confusion between preorder and inorder traversal.

💡 Preorder visits root before children; inorder visits left subtree first.

💡 Check traversal order carefully to avoid preorder mistake.

💡 Fix by visiting left subtree, then root, then right subtree.

Why it failed: Output matches preorder traversal, not inorder. Fix by changing traversal order to left-root-right.

✓ Correctly implements inorder traversal.

t4_01performance

Input{"root":[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Performance test with n=100 nodes in a skewed tree (right children only). Algorithm must run in O(n) time within 2 seconds.

💡 Inorder traversal is O(n) time and O(h) space where h is tree height.

💡 Avoid exponential or repeated work by using iterative or recursive traversal.

💡 Use Morris traversal to achieve O(1) space if needed.

Why it failed: TLE due to exponential or inefficient traversal approach. Fix by implementing O(n) traversal with recursion, stack, or Morris traversal.

✓ Traversal runs in linear time as expected.

Practice

1. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?

easy

A. Use a greedy approach by always attaching nodes as left children when possible.

B. Use dynamic programming to store subtrees and avoid recomputation.

C. Use recursion with a hash map to quickly find root indices in the inorder array.

D. Use breadth-first search to reconstruct the tree level by level.

Solution

1. Step 1: Understand the problem constraints

   Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.

2. Step 2: Evaluate approaches

   Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map lookup avoids O(n) search per recursion [OK]

Hint: Hash map lookup avoids repeated linear searches [OK]

Common Mistakes:

• Assuming greedy or BFS can reconstruct tree uniquely
• Confusing DP with tree construction
• Ignoring index lookup cost

2. Consider the following Python code implementing the optimal flatten function for a binary tree. Given the input tree: 1 / \ 2 3 What is the value of the global variable prev after the call flatten(root) completes?

easy

A. TreeNode with val=3

B. TreeNode with val=1

C. TreeNode with val=2

D. None

Solution

1. Step 1: Trace flatten calls on root=1

   flatten(1) calls flatten(3) then flatten(2). After flatten(3), prev=TreeNode with val=3; after flatten(2), prev=TreeNode with val=2; finally, root=1 sets root.right=prev (2) and prev=TreeNode with val=1.

2. Step 2: Final value of prev after flatten(1)

   After processing root=1, prev points to the root node with val=1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Global prev ends at root node after full traversal [OK]

Hint: Global prev ends at root after full flatten [OK]

Common Mistakes:

• Assuming prev ends at last leaf node
• Confusing order of recursive calls
• Forgetting prev is updated after rewiring

3. Consider the following buggy deserialization code snippet for BFS-based tree reconstruction. Which line contains the subtle bug that causes incorrect tree structure when deserializing?

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

medium

A. Line: if vals[i] != 'X': (left child check)

B. Line: i += 1 (after left child assignment)

C. Line: if vals[i] != 'X': (right child check)

D. Line: while queue: (loop condition)

Solution

1. 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.

2. 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.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must ensure 'i' stays within bounds to avoid deserialization bugs [OK]

Hint: Loop must check index bounds to avoid infinite loops [OK]

Common Mistakes:

• Not checking index bounds in deserialization loops
• Mixing up left and right child assignments
• Forgetting to append children to queue

4. Suppose the problem is modified so that the tree can have nodes with arbitrary large depth, and you want to avoid recursion stack overflow. Which approach is best to check if the tree is balanced efficiently?

hard

A. Use the brute force recursive height check since it is simpler to implement.

B. Use iterative postorder traversal with a stack to compute heights and check balance.

C. Use a breadth-first traversal and check balance at each level.

D. Use a global variable to store height and recurse with tail recursion optimization.

Solution

1. Step 1: Understand recursion stack limitations

   Deep trees can cause recursion stack overflow in recursive solutions.

2. Step 2: Identify iterative approach benefits

   Iterative postorder traversal uses explicit stack, avoiding recursion limits and still computes heights and balance in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative approach avoids recursion depth issues [OK]

Hint: Iterative traversal avoids recursion stack overflow [OK]

Common Mistakes:

• Assuming recursion with tail call optimization works in Python
• Using BFS which does not check subtree height balance
• Choosing brute force recursion despite stack limits

5. Suppose the problem is modified so that you can rob the same node multiple times (i.e., nodes can be reused any number of times), but still cannot rob directly connected nodes simultaneously. Which modification to the algorithm is necessary to correctly solve this variant?

hard

A. Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse.

B. Use the same DFS with two-value return; no changes needed since adjacency constraints remain.

C. Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection.

D. Modify the DFS to allow revisiting nodes multiple times and use memoization keyed by node and robbing state.

Solution

1. Step 1: Understand the reuse constraint

   Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.

2. Step 2: Identify necessary algorithmic change

   We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.

3. Step 3: Why other options fail

   Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Memoization with extended state handles reuse and adjacency constraints [OK]

Hint: Reuse requires stateful memoization, not simple DFS [OK]

Common Mistakes:

• Assuming original DFS suffices for reuse
• Ignoring adjacency constraints when reusing nodes