TikTok·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

TikTok software engineer interview that was basically a binary tree deep dive. They wanted both a recursive and iterative solution for in-order traversal, plus complexity analysis on the spot. Pretty standard algorithmic round but the dual-implementation requirement kept it from being totally routine.

Questions Asked (1)

Given the root of a binary tree, return the in-order traversal of its node values. Implement both a recursive solution and an iterative solution using an explicit stack, then walk through the time and space complexity of each.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The recursive version came out clean, no issues there.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clearly defining in-order traversal (left, root, right) and then present both recursive and iterative implementations. For the iterative solution, explain how an explicit stack simulates the call stack by traversing leftmost nodes first. Conclude with a detailed time and space complexity analysis for each, highlighting that both are O(n) time and O(h) space, where h is the tree height.

Pro tip: Mention that the iterative approach can be more memory-efficient for skewed trees and avoids recursion depth limits, which is crucial for production systems. Also, briefly note that Morris traversal achieves O(1) space, showing depth of knowledge.

1. Clarify the problem and traversal order

Restate that in-order traversal visits left subtree, then root, then right subtree. Confirm the expected output format (e.g., list of values).

2. Present recursive solution

Write a simple recursive function that calls itself on the left child, appends the node's value, then calls itself on the right child. Mention base case for null nodes.

3. Present iterative solution with explicit stack

Describe the algorithm: initialize an empty stack and a current pointer to root. While current is not null or stack is not empty, push all left descendants onto the stack, then pop a node, append its value, and move to its right child.

4. Analyze time and space complexity

For both solutions, time complexity is O(n) because each node is visited once. Space complexity is O(h) for recursion stack and explicit stack, where h is tree height; in worst case (skewed tree) O(n), in balanced tree O(log n).

5. Compare and discuss trade-offs

Highlight that recursive is simpler but may cause stack overflow for deep trees; iterative is more robust but requires explicit stack. Mention that both are acceptable, but iterative is often preferred in production for large trees.

Key Points to Mention

Definition of in-order traversal: left, root, right.
Recursive implementation: base case, recursive calls, and appending value.
Iterative implementation: using stack to simulate recursion, pushing left children, popping and moving right.
Time complexity: O(n) for both, as each node is processed exactly once.
Space complexity: O(h) for both, where h is tree height; worst-case O(n) for skewed tree, O(log n) for balanced tree.
Trade-offs: recursion simplicity vs. iterative robustness against stack overflow; mention Morris traversal for O(1) space as an extension.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.