Tree No-recursive Traversal

Data Structure

// Definition for a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}

• In-order Traversal (left, root, right)
  
  The output of in-order traversal of this tree is D, B, E, A, F, C, G.

  void inordertraversal(TreeNode* root) {
      if (root == NULL) return;
      TreeNode* p = root;
      stack<TreeNode*> s;
      while (!s.empty || p) {
          while (p) {
              s.push(p);
              p = p->left;
          }
          if (!s.empty()) {
              p = s.top();
              s.pop();
              cout << p->val << " ";
              p = p->rchild;
          }
      }
  }

• Pre-order Traversal (root, left, right)
  
  The output of pre-order traversal of this tree is A, B, D, E, C, F, G.

  void preordertraversal(TreeNode* root) {
      if (root == NULL) return;
      TreeNode* p = root;
      stack<TreeNode*> s;
      while (!s.empty || p) {
          while (p) {
              cout << p->val << " ";
              s.push(p);
              p = p->left;
          }
          if (!s.empty()) {
              p = s.top();
              s.pop();
              p = p->right;
          }
      }
  }

• Post-order Traversal (left, right, root)
  
  The output of post-order traversal of this tree is D, E, B, F, G, C, A.

  void postordertraversal(TreeNode* root) {
      if (root == NULL) return;
      starck<TreeNode*> s;
      TreeNode* p = root;
      TreeNode* plast = NULL;
      while (!s.empty() || p) {
          while (p) {
              s.push(p);
              p = p->left;
          }
          if (!s.empty()) {
              p = s.top();
              if (p->right && p->right != plast) {
                  p = p->right;
              } else {
                  s.pop();
                  cout << p->val << " ";
                  plast = p;
                  p = NULL;
              }
          }
      }
  }