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):

Your question is In-Order Traversal with Stack. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem