C++ tree traversals, simple and easy to understand, preorder, inorder and postorder


  • 1
    D

    Preorder :

    ​vector<int> preorderTraversal(TreeNode* root) {
                stack<TreeNode* > S;
                vector<int> V;
                if(!root)
                    return V;
                S.push(root);
                while(!S.empty()){
                    TreeNode* temp = S.top();
                    V.push_back(temp->val);
                    S.pop();
                    if(temp->right)
                        S.push(temp->right);
                    if(temp->left)
                        S.push(temp->left);
                }
                return V;
            }
    


    ​Inorder :

    vector<int> inorderTraversal(TreeNode* root) {
            stack<TreeNode*> S;
            vector<int> V;
            while(root || !S.empty()){
                while(root){
                    S.push(root);
                    root = root->left;
                }
                root = S.top();
                S.pop();
                V.push_back(root->val);
                root = root->right;
            }
            return V;
        }​
    

    ​Postorder :​

    ​vector<int> postorderTraversal(TreeNode* root) {
                stack<TreeNode*> S;
                vector<int> V;
                TreeNode *lastNode = NULL, *topNode;
                while(root || !S.empty()){
                    while(root){
                        S.push(root);
                        root = root->left;
                    }
                    topNode = S.top();
                    if(topNode->right && topNode->right != lastNode){
                        root = topNode->right;
                    }
                    else{
                        V.push_back(topNode->val);
                        lastNode = S.top();
                        S.pop();
                    }
                }
                return V;
            }​

Log in to reply
 

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