Tree Data Structure related must solve programming questions: Part - 2

Problem Statement:

Given a tree return inorder traversal of a binary tree.

Note: Solve it using both recursion and iterative approach.

Approach - 1(Recursive approach):

Recursive approach is very simple.

• Inorder traversal is traversing left sub tree first
• Then visiting root and finally visiting right sub tree.
  
• Break the recursion whenever there is no node available.

Code in C++:

class Solution {

        void traverse(TreeNode* node, vector<int> &res){

            if(!node)

                return;

            traverse(node->left, res);            

            res.push_back(node->val);            

            traverse(node->right, res);

        }

    public:

        vector<int> inorderTraversal(TreeNode* root){

            vector<int> res;

            traverse(root, res);

            return res;

        }

}

Approach - 2(Iterative approach):

Iterative approach is bit trickier than recursive approach.

• Inorder traversal is traversing left sub tree first
• Then visiting root and finally visiting right sub tree.
  
• Iterative approach can be built based on the recursive approach.
• Iterative approach can be built using the stack to store the elements.
• Approach is:
• Push root element to the stack and its left node, keep on doing this until there is no more left child
• Once after reaching end of the left sub tree, pop the top element from the stack print the element.
• Assign right child of the popped node to the current node and repeat from step 1 until the stack is non empty.

Code in C++:

/**

 * 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) {}

 * };

 */

class Solution {

public:

    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> res;

        stack<TreeNode*> elem;        

        TreeNode* curr = root;        

        while((curr) || (!elem.empty())){

            while(curr){

                elem.push(curr);

                curr = curr->left;

            } 

            curr = elem.top();

            elem.pop();

            res.push_back(curr->val);

            curr = curr->right;

        }

        return res;

    }

};