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 a binary tree and asked to transform it so that every left child becomes the right child and every right child becomes the left child, effectively mirroring the tree structure. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy traversal swapping nodes only when a certain condition is met, to minimize swaps.

B. Perform a depth-first traversal recursively, swapping left and right children after visiting subtrees.

C. Apply dynamic programming to store and reuse subtree inversion results to avoid recomputation.

D. Use breadth-first traversal with a queue, swapping children at each level iteratively.

Solution

1. Step 1: Understand the problem requires swapping children after their subtrees are inverted

   The inversion must be done bottom-up to ensure subtrees are correctly mirrored before swapping.

2. Step 2: Identify the approach that recursively inverts subtrees before swapping children

   Depth-first postorder traversal fits this pattern, ensuring correct inversion in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Postorder recursion swaps children after subtree inversion [OK]

Hint: Invert after recursive calls ensures correct subtree inversion [OK]

Common Mistakes:

• Thinking greedy swaps without recursion suffice
• Confusing DP with tree inversion
• Assuming BFS alone guarantees correct inversion

2. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 5: rob_current calculation uses left[0] and right[0]

B. Line 7: Returning (rob_current, not_rob_current)

C. Line 6: not_rob_current uses max(left) + max(right)

D. Line 2: Base case returns (0, 0)

Solution

1. Step 1: Understand rob_current calculation

   rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.

2. Step 2: Identify the bug

   Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using rob values of children overcounts and breaks correctness [OK]

Hint: Rob current node + not_rob children, not rob children [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple
• Forgetting adjacency constraints

3. What is the time complexity of the BFS-based algorithm to compute the maximum depth of a binary tree with n nodes, and why might the following common misconception be incorrect? Options:

medium

A. O(n), but with O(n) auxiliary space for the queue at the widest level

B. O(n), because each node is visited exactly once in BFS

C. O(n log n), because each level requires sorting nodes

D. O(n^2), because each node is enqueued and dequeued multiple times

Solution

1. Step 1: Identify time complexity

   BFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity and common misconception

   Queue can hold up to O(n) nodes at the widest level, so auxiliary space is O(n). The misconception is thinking nodes are processed multiple times, leading to O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node enqueued and dequeued once; max queue size O(n) [OK]

Hint: BFS visits each node once; space depends on max level width [OK]

Common Mistakes:

• Assuming multiple visits per node
• Confusing sorting with traversal
• Ignoring queue space usage

4. Consider the following buggy code for checking if a binary tree is symmetric. Which line contains the subtle bug that causes incorrect results for asymmetric trees?

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return True
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

medium

A. Line 5: if t1.val != t2.val: return False

B. Line 3: if not t1 or not t2: return True

C. Line 6: return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

D. Line 8: return isMirror(root.left, root.right) if root else True

Solution

1. Step 1: Analyze base case for null nodes

   The line returns true if either t1 or t2 is null, but it should only return true if both are null.

2. Step 2: Identify that returning true when only one node is null causes false positives

   This causes asymmetric trees with missing nodes on one side to be incorrectly considered symmetric.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Base case must check both nodes null equality, not just one [OK]

Hint: Base case must return true only if both nodes are null [OK]

Common Mistakes:

• Returning true if only one node is null
• Forgetting to check node values before recursion
• Mixing left and right subtree comparisons

5. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?

hard

A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.

B. The optimal binary search approach on the last level still applies with minor modifications.

C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).

D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.

Solution

1. Step 1: Understand the problem change

   The tree is no longer complete, so properties used by optimal methods do not hold.

2. Step 2: Identify correct counting method

   Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal methods rely on completeness, which is lost here [OK]

Hint: Without completeness, must traverse all nodes [OK]

Common Mistakes:

• Trying to apply binary search on last level
• Assuming height checks still reduce complexity