Here is the interview question prompt, presented for reference.

Can you write a function to traverse a binary tree in-order, and print out the value of each node as it passes?

  4
   \
    5
   /
  6

The example would output [4, 6, 5] since there is no left child for 4, and 6 is visited in-order before 5.

The definition of a tree node is as follows:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

public class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

struct Node {
  int val;
  Node* left = nullptr;
  Node* right = nullptr;

  Node(int val) : val(val) {}
};

public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

type Node struct {
    val   int
    left  *Node
    right *Node
}

func newNode(val int) *Node {
    return &Node{val, nil, nil}
}

Follow up: you'll likely get the recursive solution first, could you do it iteratively?

Constraints

• Number of vertices in the tree <= 100000
• The values of the vertices in the tree will be between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(1)

You can see the full challenge with visuals at this link.