Daily Dose of DSA - Day 23

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

Using Recursion :

1. The inorder function is a recursive helper function that takes a TreeNode* parameter representing the current node during traversal.

2. If the current node is NULL, the function returns, as there are no nodes to process.

3. If the current node is not NULL, the function recursively calls itself with the left child of the current node (root->left) to traverse the left subtree.

4. After the left subtree traversal, the value of the current node (root->val) is added to the ans vector, which stores the in-order traversal result.

5. Finally, the function recursively calls itself with the right child of the current node (root->right) to traverse the right subtree.

6. The recursive calls continue until all nodes in the binary tree have been traversed.

7. The inorderTraversal function is the entry point of the code. It takes a TreeNode* parameter representing the root of the binary tree.

8. Inside the inorderTraversal function, the inorder function is called to perform the in-order traversal starting from the root node.

9. Finally, the ans vector, which stores the in-order traversal result, is returned.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
vector<int> ans;
   void inorder(TreeNode*root)
   {
       if(root==NULL) return;
       inorder(root->left);
       ans.push_back(root->val);
       inorder(root->right);
   }
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root);
        return ans;
    }
};

Using Stack with Iteration :

1. The inorderTraversal function takes a TreeNode* parameter root, representing the root of the binary tree.

2. Inside the function, a stack of TreeNode* named st is created to perform iterative in-order traversal.

3. A TreeNode* variable node is initialized with the value of root, indicating the current node during traversal.

4. An empty vector ans is initialized to store the in-order traversal result.

5. The code enters an infinite loop that breaks when both the stack is empty and node is NULL.

6. Inside the loop, if node is not NULL, it means there are more left nodes to traverse. In this case, the current node is pushed onto the stack using st.push(node) and node is updated to its left child node->left.

7. If node is NULL, it means there are no more left nodes to traverse. In this case, the code checks if the stack is empty. If it is, it breaks the loop as all nodes have been processed.

8. If the stack is not empty, the top node node is popped from the stack using st.top() and removed using st.pop(). Its value node->val is added to the ans vector, capturing the in-order traversal sequence.

9. After adding the current node to the ans vector, node is updated to its right child node->right.

10. The loop continues until all nodes in the binary tree have been processed.

11. Finally, the function returns the ans vector containing the in-order traversal result.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*>st;
        TreeNode* node = root;
        vector<int> ans;
        while(true)
        {
            if(node!=NULL)
            {
                st.push(node);   
                node = node->left;
            }
            else
            {
                if(st.empty()) break;
                node = st.top();
                st.pop();
                ans.push_back(node->val);
                node = node->right;
            }
        }
       return ans;
    }
};