Tree

Tree Traversal

BFS

• Level Order

BFS

• preorder : root -> left -> right

  • Prefix expression are generated from expressoin tree of the expression.
  • A copy of the tree is generated from preorder traverse.

  void preorderIterative(Node* root) {
      if (root == NULL) return;
  
      stack<Node*> st;
      st.push(root);
  
      while (!st.empty()) {
          Node* current = st.top();
          st.pop();
  
          cout << current->data << " ";
  
          if (current->right)
              st.push(current->right);
  
          if (current->left)
              st.push(current->left);
      }
  }

• inorder : left -> root -> right

  • Expression are extracted from inorder tree of the expressoin.
  • In BST, to extract item in non-decresing order, perform reverse inorder(HOW)

  void inorder(Node* root) {
      stack<Node*> st;
      Node* current = root;
  
      while (current != NULL || !st.empty()) {
  
          // Go to leftmost node
          while (current != NULL) {
              st.push(current);
              current = current->left;
          }
  
          current = st.top();
          st.pop();
  
          cout << current->data << " ";
  
          current = current->right;
      }
  }

• postorder: left -> right -> root

  • Post expression are generated from expressoin tree of the expression.

  // One Stack
  void postorder(Node* root) {
      if (root == NULL) return;
  
      stack<Node*> st1, st2;
      st1.push(root);
  
      while (!st1.empty()) {
          Node* current = st1.top();
          st1.pop();
  
          st2.push(current);
  
          if (current->left)
              st1.push(current->left);
  
          if (current->right)
              st1.push(current->right);
      }
  
      while (!st2.empty()) {
          cout << st2.top()->data << " ";
          st2.pop();
      }
  }
  
  // Two Stack
  void postorder(Node* root) {
      if (root == NULL) return;
  
      stack<Node*> st;
      Node* current = root;
      Node* lastVisited = NULL;
  
      while (current != NULL || !st.empty()) {
  
          if (current != NULL) {
              st.push(current);
              current = current->left;
          }
          else {
              Node* peekNode = st.top();
  
              if (peekNode->right != NULL && lastVisited != peekNode->right) {
                  current = peekNode->right;
              }
              else {
                  cout << peekNode->data << " ";
                  lastVisited = peekNode;
                  st.pop();
              }
          }
      }
  }