void in_order_traversal_iterative(BinaryTree *root) {
Posts Tagged ‘bst’
Inorder traversal of a Binary Search Tree without recursion
Posted by guptaradhesh on May 16, 2013
Posted in puzzles/ algorithms  Tagged: binary search tree, bst, traversal  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
}

Posted in puzzles/ algorithms, tech  Tagged: binary search tree, bst, lowest common ancestor, lsa, recursion  Leave a Comment »
create Mirror of a Binary Tree
Posted by guptaradhesh on December 8, 2010
a solution pseudocode 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);
}
Posted in puzzles/ algorithms  Tagged: algorithm, bst, mirror of a binary tree  Leave a Comment »
The maximum size of the child subtree of a binary complete tree of size n is 2n/3
Posted by guptaradhesh on October 20, 2010
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 ith level of T2, then the ith level of T1 is full.
> By previous point, we may assume that T1 and T2 are both full in their 1st to jth 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.
Posted in puzzles/ algorithms  Tagged: 2n/3, binary tree, bst, size, subtree  2 Comments »