Tree Gists: (1) find the lowest common ancestor of a Binary Tree (2) determine if a Binary Tree is BST or not (3) Inorder Traversal (4) Preorder Traversal (5) Postorder Traversal (6) Inorder without stack or recursive

checkBST.cc

struct Node {
  Node *left;
  Node *right;
  int _data;
  Node(int data) : _data(data), left(NULL), right(NULL) {}
};

bool checkBST(Node *root) {
  return help(root, INT_MIN, INT_MAX);
}

bool help(NOde *root, int left, int right) {
  if (root == NULL)
    return true;
    
  if (root->_data <= left || root->_data > right)
    return false;
    
  else
    return help(root->left, left, root->_data) && help(root->right, root->_data, right);
}

inOrder.cpp

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int value) : val(value), left(NULL), right(NULL) {};
};

void InOrder(TreeNode *root) {
  
  stack<TreeNode *> the_stack;
  bool done = false;
  TreeNode *curr = root;
  
  while (done == false) {
    if (curr) {
      the_stack.push_back(curr);
      curr = curr->left;
    }
    else {
      if (the_stack.empty())
        done = true;
      else {
        curr = the_stack.top();
        the_stack.pop();
        // process curr
        curr = curr->right;
      }
    }
  }
}

lowestCommonAncestor.cpp

struct Node {
  int val;
  Node *left;
  Node *right;
  Node(int value) : val(value), left(NULL), right(NULL) {};
};

Node *LCA(Node *root, Node *first, Node *second) {
    
  if (root == NULL || root == first || root == second)
    return root;
    
  Node *left = LCA(root->left, first, second);
  Node *right = LCA(root->right, first, second);
  
  if (left && right)
    return root;
  else
    return left?left:right;
}

postOrder.cc

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int value) : val(value), left(NULL), right(NULL) {}
};

void PostOrderTraversal(TreeNode *root) {
  
  if (root == NULL)
    return;
    
  stack<TreeNode *> the_stack;
  the_stack.push(root);
  TreeNode *prev = NULL:
  
  while (!the_stack.empty()) {
    TreeNode *curr = the_stack.pop();
    // we are traversing down the tree
    if (prev == NULL || prev->left == curr || prev->right == curr) {
      if (curr->left)
        the_stack.push(curr->left);
      else if (curr->right)
        the_stack.push(curr->right);
      else {
        // process curr
        the_stack.pop();
      }
    }
    // we are traversing up the tree from left
    else if (curr->left == prev) {
      if (curr->right)
        the_stack.push(curr->right);
      else {
        // process curr
        the_stack.pop();
      }
    }
    // we are traversing up the tree from right
    else {
      // process curr
      the_stack.pop();
    }
    prev = curr;
  }
}

preOrder.cpp

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int value) : val(value), left(NULL), right(NULL) {};
};

void PreOrder(TreeNode *root) {
  if (root == NULL)
    return;
    
  stack<TreeNode *> the_stack;
  
  the_stack.push(root);
  
  while (!the_stack.empty()) {
    TreeNode *curr = the_stack.top();
    the_stack.pop();
    // process curr;
    
    if (curr->right)
      the_stack.push(curr->right);
    if (curr->left)
      the_stack.push(curr->left);
  }
}