Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoftGoogle

Binary Tree Inorder Traversal

Choose your preparation mode4 modes available
📋
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
}
0/10
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
t1_01basic
Input{"root":[1,null,2,3]}
Expected[1,3,2]

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

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

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

t2_01edge
Input{"root":null}
Expected[]

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

t2_02edge
Input{"root":[42]}
Expected[42]

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

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

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

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

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

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

Balanced tree inorder traversal visits nodes in sorted order.

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

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

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

Test to catch confusion between preorder and 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]}
⏱ 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.

Practice

(1/5)
1. Given a binary tree where each root-to-leaf path represents a number formed by concatenating node values, which algorithmic approach guarantees computing the sum of all such numbers efficiently without missing any path or double counting partial paths?
easy
A. Depth-first search (DFS) that accumulates the current number along the path and adds it only at leaf nodes
B. Dynamic programming that stores sums for subtrees and combines them at the root
C. Greedy traversal that sums node values at each level independently
D. Breadth-first search (BFS) that sums values of nodes at each depth and multiplies by depth

Solution

  1. Step 1: Understand problem requirements

    The problem requires summing numbers formed by concatenating node values from root to leaf, so partial paths must not be summed prematurely.
  2. Step 2: Identify correct traversal pattern

    DFS naturally explores root-to-leaf paths, allowing accumulation of the current number and summing only at leaf nodes, ensuring correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS accumulates path values correctly and sums only at leaves [OK]
Hint: Sum only at leaves during DFS traversal [OK]
Common Mistakes:
  • Summing at non-leaf nodes
  • Using BFS without path tracking
2. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?
medium
A. Line 1: Missing check for empty root before traversal
B. Line 7: Incorrectly pushing node.left without null check
C. Line 12: Comparing last_visited with peek.right incorrectly
D. Line 16: Using abs difference without considering null children

Solution

  1. Step 1: Identify handling of empty tree

    The code does not check if root is None before starting traversal, which can cause errors or incorrect results.
  2. Step 2: Verify other lines

    Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing early return for empty root causes bug [OK]
Hint: Always check for empty root before traversal [OK]
Common Mistakes:
  • Forgetting to handle empty tree as balanced
  • Incorrectly comparing last_visited causing infinite loops
  • Not defaulting heights for null children
3. Examine the following buggy code snippet for computing the maximum path sum in a binary tree. Which line contains the subtle bug that causes incorrect results on trees with negative node values?
def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max_gain(node.left)
        right_gain = max_gain(node.right)
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)
        # Bug: returns sum of both left and right gains to parent
        return node.val + left_gain + right_gain

    max_gain(root)
    return max_sum
medium
A. Line returning 0 for null node
B. Line computing current_path_sum = node.val + left_gain + right_gain
C. Line updating max_sum = max(max_sum, current_path_sum)
D. Line returning node.val + left_gain + right_gain

Solution

  1. Step 1: Understand return value meaning

    The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).
  2. Step 2: Identify the bug

    Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Return should be node.val + max(left_gain, right_gain) [OK]
Hint: Return value must be single path gain, not sum of both children [OK]
Common Mistakes:
  • Returning sum of both children gains
  • Ignoring negative gains
  • Updating max_sum incorrectly
4. Consider this buggy iterative postorder traversal code:
def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result
What is the bug in this code?
medium
A. The inner while loop should traverse right children instead of left
B. The condition should check if last_visited != peek_node.right, not == peek_node.right
C. The last_visited variable is never updated
D. The result list is appended before traversing the left subtree

Solution

  1. Step 1: Examine condition for traversing right subtree

    Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.
  2. Step 2: Identify effect of wrong condition

    Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Fixing condition restores correct postorder traversal [OK]
Hint: Check last_visited != right child to avoid revisiting [OK]
Common Mistakes:
  • Using == instead of !=
  • Not updating last_visited
  • Appending too early
5. Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:
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
medium
A. Line resetting predecessor.right to None is missing in the else block
B. Appending current.val before moving to left child is incorrect
C. The inner while loop condition should check predecessor.left instead of predecessor.right
D. The check for current.left being None should be after the else block

Solution

  1. 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.
  2. Step 2: Locate missing line

    The else block lacks the line predecessor.right = None, causing the threaded link to persist.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without resetting, tree remains modified after traversal [OK]
Hint: Always reset threaded links to None after use [OK]
Common Mistakes:
  • Forgetting to restore tree structure
  • Appending nodes in wrong order
  • Incorrect loop conditions
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard