In-order traversal of a Binary Search Tree without recursion

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

Lowest common ancestor of a Binary Search Tree

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

 

create Mirror of a Binary Tree

a solution pseudo-code to this using recursion is as:

mynode *createMirror (mynode *root)
{
mynode *temp;

if(root==NULL)return(NULL);

temp = (mynode *) malloc(sizeof(mynode));
temp->value = root->value;

temp->left = createMirror(root->right);
temp->right = createMirror(root->left);

return(temp);
}

The maximum size of the child subtree of a binary complete tree of size n is 2n/3

The maximum size of the child subtree of a binary complete tree of size n is 2n/3.  This is also a problem P.131 of the CLR. I liked the approach of proving things given by my TA and then I completed the proof. Here is all-

> The root has two child subtrees – the left one and the right one. Let’s call these subtrees T1 (the left one) and T2 (the right one). One very important property of heap is, in every level, the elements are packed to the leftmost. So if there is an element in the i-th level of T2, then the i-th level of T1 is full.
> By previous point, we may assume that T1 and T2 are both full in their 1st to j-th level, and there are some extra elements in the (j+1)-st level of T1 and T2.
> Here we become greedy. We know that size(T1) >= size(T2), and we want size(T1) as large as possible and size(T2) as small as possible (so that T1 will occupy a greater portion of the total tree). To be greedy, we want the (j+1)-st level of T1 be full, and the (j+1)-st level of T2 be empty.

Now, for this case, let X be the elements in right subtree of a node. Then number of elements in left subtree is X+X = 2X (elements till second last level + elements in last level). Total number of elements = 2X+X = 3X.

So, maximum number of elements a child subtree can have = 2X = 2/3(3X)

Hence Justified.