Implement binary tree in-order traversal
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given the root of a binary tree, return the in-order ordering of its node values. Implement both a recursive solution and an iterative solution using an explicit stack, and analyze their time and space complexity.
Quick Answer: This question evaluates understanding of binary tree traversal, comparing recursive and iterative (explicit stack) implementations and their time and space complexity. Commonly asked in Coding & Algorithms interviews to assess both practical implementation and conceptual understanding of tree data structures, algorithmic trade-offs, and complexity analysis.
Given the root of a binary tree, return the in-order traversal of its node values (left subtree, node, right subtree).
The tree is provided as a level-order (breadth-first) array `level_order`, using `null`/`None` to mark missing children — the same encoding LeetCode uses. For example, `[1, null, 2, 3]` represents the tree whose root is 1, with no left child, a right child 2, and 2's left child 3.
Return a list of the node values in in-order.
This is LeetCode 94. Try to implement it both recursively and iteratively with an explicit stack; the reference solution shown uses the iterative approach.
Constraints
- The number of nodes is in the range [0, 100].
- -100 <= Node.val <= 100
- Missing children are encoded as null/None in the level-order array.
Examples
Input: ([1, None, 2, 3],)
Expected Output: [1, 3, 2]
Explanation: Tree: 1 has right child 2, and 2 has left child 3. In-order visits 1, then 2's left (3), then 2 -> [1, 3, 2].
Input: ([],)
Expected Output: []
Explanation: Empty tree yields an empty traversal.
Hints
- Recursive: in-order is 'traverse left, visit node, traverse right'. The base case is an empty (null) subtree.
- Iterative: walk left as far as possible while pushing nodes onto a stack; when you can't go further, pop a node, record its value, then move to its right child and repeat.
- Time is O(n) for both approaches; the iterative stack (or the recursion call stack) uses O(h) extra space, which is O(n) worst case for a skewed tree.