Ninja technique🥷 to ACE DSA Interviews.
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return NULL;
// Swap left and right children
// swap(node->left, node->right);
TreeNode* temp;
temp = root->left;
root->left = root->right;
root->right = temp;
invertTree(root->left);
invertTree(root->right);
return root;
}
};
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (node) {
st.push(node->left);
st.push(node->right);
swap(node->left, node->right);
}
}
return root;
}
};
The ans is simple, Tree can be skewed which effectively makes it a linked list. And if we recurse in a large linked-list, the call stack will overflow for sure. That’s why its necessary to also know how to implement iteratively. Honestly, iterative implementation also will utilize a stack, but it will be in heap.