..MindWrite..

Posts Tagged ‘binary search tree’

In-order traversal of a Binary Search Tree without recursion

Posted by guptaradhesh on May 16, 2013

void in_order_traversal_iterative(BinaryTree *root) {

  stack<BinaryTree*> s;
  BinaryTree *current = root;
  while (!s.empty() || current) {
    if (current) {
      s.push(current);
      current = current->left;
    } else {
      current = s.top();
      s.pop();
      cout << current->data << ” “;
      current = current->right;
    }
  }
}
reference: here
Advertisements

Posted in puzzles/ algorithms | Tagged: , , | Leave a Comment »

Lowest common ancestor of a Binary Search Tree

Posted by guptaradhesh on May 16, 2013


Worst case O(n

1.
2
3
4
5
6
7
8
Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}
  —
reference: here
 

Posted in puzzles/ algorithms, tech | Tagged: , , , , | Leave a Comment »