In-Order Traversal with Stack | Dataford Interview Questions

Implement in-order traversal using a stack, optimize it, and explain time and space complexity.

Asked in the Technical 2 stage.

Contract

Implement inorder_traversal(root). The input is a binary tree represented by nested dictionaries with keys "val", "left", and "right"; an empty child is None. Return a list of node values in left-root-right order. Use an iterative stack-based approach rather than recursion.

Example 1: {"val": 2, "left": {"val": 1, "left": null, "right": null}, "right": {"val": 3, "left": null, "right": null}} returns [1, 2, 3].

Example 2: None returns [].

Constraints: at most 10^4 nodes, values are integers, and the tree may be skewed.

Constraints

0 <= number of nodes <= 10^4
Each node value is an integer
Each node has keys "val", "left", and "right"
Child references are either another node dictionary or None

Function Signature

def inorder_traversal(root):

Whenever you're ready, walk me through your approach or go straight to the code. The requirements are in the Question tab.

Problem