DEV Community

dinhluanbmt
dinhluanbmt

Posted on • Edited 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) {}
  };
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode
  • 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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;     
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay