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

## Top comments (0)