Traversal / comparison (Tree DFS Sub-pattern)

// Recursive DFS: the three orders differ only in WHERE you handle the node.
void dfs(TreeNode* node, vector<int>& out) {
    if (!node) return;
    // preorder:  out.push_back(node->val);   (node before its children)
    dfs(node->left, out);
    out.push_back(node->val);                 // inorder: between the two children
    dfs(node->right, out);
    // postorder: out.push_back(node->val);  (node after both children)
}

// Iterative inorder with your own stack: go left as far as possible, then visit, then go right.
vector<int> inorderIterative(TreeNode* root) {
    vector<int> out;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }   // everything on the way down waits its turn
        cur = st.top(); st.pop();
        out.push_back(cur->val);                         // its whole left side is already done
        cur = cur->right;
    }
    return out;
}

// Two trees at once: compare the pair, then recurse on matching pairs of children.
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p || !q) return p == q;                         // both null → same; one null → different
    return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}