49. Binary Tree Inorder Traversal

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res, stack, node = [], [], root
        while node or stack:
            while node:              # go as far left as possible
                stack.append(node)
                node = node.left
            node = stack.pop()       # visit
            res.append(node.val)
            node = node.right        # then the right subtree
        return res

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) { stack.push(node); node = node.left; }
            node = stack.pop();
            res.add(node.val);
            node = node.right;
        }
        return res;
    }
}

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        vector<TreeNode*> st;
        TreeNode* node = root;
        while (node || !st.empty()) {
            while (node) { st.push_back(node); node = node->left; }
            node = st.back(); st.pop_back();
            res.push_back(node->val);
            node = node->right;
        }
        return res;
    }
};

function inorderTraversal(root) {
  const res = [], stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop();
    res.push(node.val);
    node = node.right;
  }
  return res;
}