## DEV Community

dinhluanbmt

Posted on • Updated on

# C++ - Basic Tree Traversal(Recursive vs Stack)

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) {}
};
``````

Main types of binary tree traversal:

• Inorder (Traversal): left - root - right
• Preorder(Traversal): root - left - right
• Postorder(Traversal): left - right - root

leetcode question :
94. Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values.

• Recursive Solution
``````class Recursive_Solution {
public:
void travel(vector<int>& tree, TreeNode* root) {
if (!root) return;
travel(tree, root->left);
tree.push_back(root->val);
travel(tree, root->right);

}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
travel(ret, root);
return ret;
}
};
``````
• Non Recursive (using stack)
``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> mst;
vector<int> ret;
TreeNode* tn = root;
while (tn || !mst.empty()) {
while (tn) {
mst.push(tn);
tn = tn->left;
}
tn = mst.top();
ret.push_back(tn->val);
mst.pop();
tn = tn->right;
}
return ret;
}
};
``````

Leetcode question:
98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Non Recursive (using Stack)

``````class Solution_stack {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* tn = root;
TreeNode* prv = nullptr;
while(tn || !st.empty()){
while(tn){
st.push(tn);
tn = tn->left;
}
tn = st.top();
st.pop();
if(prv){
if(prv->val >= tn->val) return false;
}
prv = tn;
tn = tn->right;
}
return true;
}
};
``````

Recursive solution

``````class Solution_recursive {
public:
bool g_ret = true;
TreeNode* prv = nullptr;
void check(TreeNode* root){
if(!root) return;
if(root->left) check(root->left);
if(prv){
if(prv->val >= root->val) {g_ret = false; return;}
}
prv = root;
check(root->right);
}
bool isValidBST(TreeNode* root) {
check(root);
return g_ret;
}
};
``````