C++ 0ms Recursive and Non-Recursive (DFS Stack) Solution

  • 0

    Recursive solution recurses on left child, then right child, then adds the current node's value to the array.

    The iterative solution uses depth-first search implemented with a stack. Nodes are added as a pair<TreeNode*, bool> with the bool set to false (it's children have not been added to the stack). If the pair at the top of the stack has bool == false, it adds the current pair, the right child pair and left child pair to the stack in that order (i.e. when popped, it will return left->right->parent); if bool == true then it adds the value to the array.

    class Solution {
        void traverse(TreeNode* curr, vector<int> &vals) {  //recursive solution
            if(curr != NULL) {
                traverse(curr->left, vals);
                traverse(curr->right, vals);
        vector<int> postorderTraversal(TreeNode* root) {    
            vector<int> vals;
            if (root == NULL) return vals;
            //traverse(root, vals);   //recursive solution
            stack<pair<TreeNode*, bool>> dfs;   //iterative solution
            dfs.push(pair<TreeNode*, bool>(root, false));
            while (!dfs.empty()) {
                pair<TreeNode*, bool> curr = dfs.top(); dfs.pop();
                if (curr.first != NULL && curr.second == false) {
                    curr.second = true;
                    dfs.push(pair<TreeNode*, bool>(curr.first->right, false));
                    dfs.push(pair<TreeNode*, bool>(curr.first->left, false));
                else if (curr.second == true) {
            return vals;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.