Similar problems: LC 285. Inorder Successor in BST, LC 230. Kth Smallest Element in a BST
Straightforward Recursive inorder traversal
Doing an inorder traversal of a binary tree is pretty straightforward recursively.
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
helper(root, ans);
return ans;
}
void helper(TreeNode* root, vector<int>& ans) {
if (!root)
return;
helper(root->left, ans); // visit left subtree
ans.push_back(root->val); // push root to ans after completing left subtree
helper(root->right, ans); // visit right subtree
}
Follow up: Iterative inorder traversal
We essentially have to simulate the recursive process in an iterative manner. A clear choice for simulating recursive calls is using a stack. Now, how does the iterative inorder traversal work?
Starting from the given root node of the tree:
- Go as left as possible pushing the nodes in a stack (until the encountered node’s left child is NULL).
- Pop the node which is on top of the stack
- Push the node to the answer and check:
- if the node has a right child, push the right child to the stack and then go to step 1 (essentially we are now traversing the right subtree of the previous node as we have already visited the left subtree and also the root)
- else repeat step 2
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
if (root == NULL)
return ans;
s.push(root);
// step 1. go as left as possible
while (root->left) {
root = root->left;
s.push(root);
}
while (!s.empty()) {
// step 2
TreeNode* top = s.top();
s.pop();
ans.push_back(top->val);
// step 3 check
if (top->right) {
top = top->right;
s.push(top);
while (top->left) {
top = top->left;
s.push(top);
}
}
}
return ans;
}
Concise code:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
if (root == NULL)
return ans;
while (!s.empty() || root) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
return ans;
}