DEV Community

Thivyaa Mohan
Thivyaa Mohan

Posted on

Iterative Inorder Traversal - Leetcode

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        //first, we create a stack 
        stack<TreeNode*>st;
        //create a node and assign it to root 
        TreeNode*node = root;
        //declare a vector which stores inorder 
        vector<int>inorder;
        while(true){
        //if the node that is the root is not null, we take that and insert it into stack
            if(node != NULL){
                st.push(node);
        //after pushing into stack, move to the left 
                node = node->left;
            }
            else{
            //if you traverse a tree and end up getting null, this is what you need to do 
            //if stack is empty there are no nodes to travel
                if(st.empty() == true) break;
            //else if the st is not empty, whatever is at the top we will take it 
                node = st.top();
                st.pop();
            //and this is eventually inorder
                inorder.push_back(node->val);
                node = node->right;
            }

        }
        return inorder;
    }
};

//TC :O(n) , as we traverse every node 
// SC :O(h) , height of the binary tree, in worst case it is skewed tree
Enter fullscreen mode Exit fullscreen mode

Top comments (0)