Starting from root
node and moving downwards if you find any node that has either p
or q
as its direct child then it is the LCA. (edit - this should be if p
or q
is the node's value, return it. Otherwise it will fail when one of p
or q
is a direct child of the other.)
Else if you find a node with p
in its right(or left) subtree and q
in its left(or right) subtree then it is the LCA.
The fixed code looks like:
treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {
// no root no LCA.
if(!root) {
return NULL;
}
// if either p or q is the root then root is LCA.
if(root==p || root==q) {
return root;
} else {
// get LCA of p and q in left subtree.
treeNodePtr l=findLCA(root->left , p , q);
// get LCA of p and q in right subtree.
treeNodePtr r=findLCA(root->right , p, q);
// if one of p or q is in leftsubtree and other is in right
// then root it the LCA.
if(l && r) {
return root;
}
// else if l is not null, l is LCA.
else if(l) {
return l;
} else {
return r;
}
}
}
The below code fails when either is the direct child of other.
treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {
// no root no LCA.
if(!root) {
return NULL;
}
// if either p or q is direct child of root then root is LCA.
if(root->left==p || root->left==q ||
root->right ==p || root->right ==q) {
return root;
} else {
// get LCA of p and q in left subtree.
treeNodePtr l=findLCA(root->left , p , q);
// get LCA of p and q in right subtree.
treeNodePtr r=findLCA(root->right , p, q);
// if one of p or q is in leftsubtree and other is in right
// then root it the LCA.
if(l && r) {
return root;
}
// else if l is not null, l is LCA.
else if(l) {
return l;
} else {
return r;
}
}
}
Code In Action
Your analysis is wrong, both insertion and deletion is O(n) for a sorted array, because you have to physically move the data to make space for the insertion or compress it to cover up the deleted item.
Oh and the worst case for completely unbalanced binary search trees is O(n), not O(logn).
Best Answer
Here's just an outline of the idea:
In a BST, the left subtree of node
T
contains only elements smaller than the value stored inT
. Ifk
is smaller than the number of elements in the left subtree, thek
th smallest element must belong to the left subtree. Otherwise, ifk
is larger, then thek
th smallest element is in the right subtree.We can augment the BST to have each node in it store the number of elements in its left subtree (assume that the left subtree of a given node includes that node). With this piece of information, it is simple to traverse the tree by repeatedly asking for the number of elements in the left subtree, to decide whether to do recurse into the left or right subtree.
Now, suppose we are at node T:
T
.k
th smallest. So, we reduce the problem to finding thek - num_elements(left subtree of T)
smallest element of the right subtree.k
th smallest is somewhere in the left subtree, so we reduce the problem to finding thek
th smallest element in the left subtree.Complexity analysis:
This takes
O(depth of node)
time, which isO(log n)
in the worst case on a balanced BST, orO(log n)
on average for a random BST.A BST requires
O(n)
storage, and it takes anotherO(n)
to store the information about the number of elements. All BST operations takeO(depth of node)
time, and it takesO(depth of node)
extra time to maintain the "number of elements" information for insertion, deletion or rotation of nodes. Therefore, storing information about the number of elements in the left subtree keeps the space and time complexity of a BST.