How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Implement binary tree in-order traversal

Quick Overview

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.

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.

Input: ([1],)

Expected Output: [1]

Explanation: Single node tree yields just its value.

Input: ([4, 2, 6, 1, 3, 5, 7],)

Expected Output: [1, 2, 3, 4, 5, 6, 7]

Explanation: A balanced BST; in-order traversal of a BST yields values in sorted order.

Input: ([1, 2, None, 3, None, 4],)

Expected Output: [4, 3, 2, 1]

Explanation: A fully left-leaning chain 1->2->3->4; in-order visits the deepest left node first -> [4, 3, 2, 1].

Input: ([-10, -20, 30, None, -25],)

Expected Output: [-20, -25, -10, 30]

Explanation: Negative values: root -10, left -20 (with right child -25), right 30. In-order -> [-20, -25, -10, 30].

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.

Quick Overview