dev-resources.site

for different kinds of informations.

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

Published at

8/1/2023

Categories

4 categories in total

Author

11 person written this

dinhluanbmt

open

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

tree Article's

30 articles in total