Nearest common Ancestor Given a binary tree(not a BST), you need to find the Nearest common ancestor of the two given values.

/* InOrder Traversal Left ==> ROOT ==> RIGHT , hence the NCA of 2 nodes should be inbetween the 2 nodes in the vector. PostOrder traversal LEFT ==> RIGHT ==> ROOT , hence the NCA is the leftmost in postOrder vector of all the elements found inbetween in INOrder vector */ int nca(BinaryTreeIntNode* node,int n1,int n2) { if(node == NULL) { return -1; } int nca = -1; std::vector* vectInorder = new std::vector(); std::vector* vectPost = new std::vector(); InOrderRecVector(node,vectInorder);//get the inOrder traversal in a Vector postOrderRecVector(node,vectPost);//get the postOrder traversal in a Vector int tempIndex = 0; int index1 = std::find(vectInorder->begin(),vectInorder->end(),n1) - vectInorder->begin(); int index2 = std::find(vectInorder->begin(),vectInorder->end(),n2) - vectInorder->begin(); int i = (index1>index2?index1:index2); int j = (index1>index2?index2:index1); for(i; i >= j;i--) { tempIndex = std::find(vectPost->begin(),vectPost->end(),vectInorder->at(i))-vectPost->begin(); nca = nca>tempIndex?nca:tempIndex; } if(nca==-1) { return -1; } cout<<" The NCA of "<< n1 <<" and "<< n2<< " = "<at(nca)<at(nca); }

Diameter of a binary tree

Given a binary tree you need to find the diameter of the binary tree. Diameter is defined as the maximum distance possible between any two nodes in the binary tree (It is implicit that the nodes will be the leaf nodes of the tree).

int LintkedIntTree::diameter(BinaryTreeIntNode* node) { if(node == NULL) { return 0; } int hl=heightRec(node->left); int hr=heightRec(node->right); int ld=diameter(node->left); int lr=diameter(node->right); return (ld>lr?ld:lr)>(hl+hr+1)?(ld>lr?ld:lr):(hl+hr+1); }