Daily Dose of DSA - Day 22

Question Link: https://leetcode.com/problems/binary-tree-preorder-traversal/description/

Using Recursion :

1. The preorder 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, its value (root->val) is added to the ans vector, which stores the pre-order traversal result.

4. The function then recursively calls itself with the left child of the current node (root->left) to traverse the left subtree.

5. After the left subtree traversal, 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 preorderTraversal function is the entry point of the code. It takes a TreeNode* parameter representing the root of the binary tree.

8. Inside the preorderTraversal function, the preorder function is called to perform the pre-order traversal starting from the root node.

9. Finally, the ans vector, which stores the pre-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 preorder(TreeNode* root)
  {
      if(root==NULL) return;
      ans.push_back(root->val);
      preorder(root->left);
      preorder(root->right);

  }
    vector<int> preorderTraversal(TreeNode* root) {
        preorder(root);
        return ans;
    }
};

Using Stack with Iteration:

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

2. Inside the function, an empty vector ans is initialized to store the pre-order traversal result.

3. If the root is NULL, indicating an empty tree, the function directly returns the empty ans vector.

4. If the root is not NULL, a stack of TreeNode* named st is created to perform iterative pre-order traversal. The stack is initially populated with the root node.

5. While the stack is not empty, the function enters a loop to process the nodes.

6. In each iteration of the loop, the top node x is popped from the stack using st.top() and removed using st.pop().

7. The value of the popped node x->val is added to the ans vector, capturing the pre-order traversal sequence.

8. If the popped node x has a right child (x->right is not NULL), it is pushed onto the stack to be processed later.

9. If the popped node x has a left child (x->left is not NULL), it is also pushed onto the stack to be processed later.

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

11. Finally, the function returns the ans vector containing the pre-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> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root==NULL) return ans;
        stack<TreeNode*>st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* x = st.top();
            ans.push_back(x->val);
            st.pop();
            if(x->right!=NULL) st.push(x->right);
            if(x->left!=NULL) st.push(x->left);
        }

        return ans;
    }
};