CareerCup

Node* getSecondLargestNode( Node* root )
{
   if ( !root || !root->right)
   {
      return NULL;
   }
   
   Node* parent = root;
   Node* rightNode = parent->right;
   while ( rightNode->right != NULL )
   {
      parent = rightNode;
      rightNode = parent->right;
   }
   return parent;
}

Just do an inorder traversal and grab the 2nd to last.

void inorderTraverse( Node* root, vector<Node*>& nodes )
{
   if ( !root )
      return;
   inorderTraverse( root->left, nodes );
   nodes.push_back( root );
   inorderTraverse( root->right, nodes );
}

Node* getSecondLargestNode( Node* root )
{
   vector<Node*> inorderTraversal;
   inorderTraverse( root, inorderTraversal );
   if ( inorderTraversal.size() < 2 )
      return NULL;
   else
      return inorderTraversal[inorderTraversal.size() - 2];
}

First code post doesn't account for this case:

10
    /
   5
    \
     8

Second post is good, but requires whole tree traversal, with memory storage n.

How about this:

Node * secondLargest(Node* root)
{
	if (!root)
		return NULL;
	else if (!root->right)
		return maxValue(root->left);
	else if (!root->right->right)
		return root;
	else
		return secondLargest(root->right);
}

where maxValue is a function that returns the right most node.

Why is it not the parent of the largest node?

find the largest node(logN), then find its predecessor(logN)

node* getSecondHighestNode( node* root)
{
if(!root)
return NULL;

int max;
node* cur = root;
while(cur->right)
{
cur = cur->right;
}
max = cur->data;

node* secondMax = NULL;
cur = root;

while(cur)
{
if(cur->data < max)
{
secondMax = cur;
cur = cur-> right;
}
else
cur = cur-> left;
}
return secondMax;
}

why the hell people are wasting tiem for such silly quesitons....as some one already mentioend do a simple DFS/BFS and pick the penultimate node and u are done = O(n)
else do it this way...
pick the max and delete it = O(logn) + O(1)
now pick the max again = O(logn)
Total run time = O(logn)
as the quesiton dint say that we're not allowed to modify the tree, the above solution should do the job...and runs in O(logn)..thats good enough~!

node* find_max(node* t)
{
while(t->right)
t = t->right;

return t;
}

void find_secondMax(node* root)
{

node* max = find_max(root);

if (max->left)
return find_max(max->left);
else
return max->parent;
}

public void FindSecondMax()
{
FindSecondMax(Root);
}

public void FindSecondMax(TreeNode tn)
{

if (tn.Right != null)
FindSecondMax(tn.Right);

if (i == 2)
Console.WriteLine("Second Largest{0}", tn.Value);
i++;

if (tn.Left != null)
FindSecondMax(tn.Left);
}

Two cases :
1. Parent node is the largest node.
Parent node can be either a normal parent or a root.
return its immediate left child as the SecondLargest.
2. Right most is the largest node.
return its parent as the SecondLargest.

code:
=====

void SecondLargest(node *root, int *secondLargest)
{
	if(!root)	
		return;
	if(!SecondLargest(root->right))
	{
		if(!secondLargest)
		{
			if(!root->right->left)
				*secondLargest = root->right->left->value; //if the parent is the largest then its immediate left is the second largest
			else
				*secondLargest = root->value;	//if the rightmost child is the largest then its parent is the secondlargest
		}
	}
	if(!secondLargest)	//if root is the largest node (ie)left oriented tree
	{
		if(!root->left)
			*secondLargest = (root->left->value);
		else
			return;	//tree with only root node
	}
	return;
}

cant we construct a heap and get max node?//

void visit(NODE* node)
{
static int item=0;

item++;
if (item==2) print(node);
}

void inorder(NODE* root)
{
if (!root) return;
if (root->right) inorder(root->right);
visit(root);
if (root->left) inorder(root->left);
}

goto the node which has max element...if that node has left subtree then return the max element of that subtree ...else return the parent of the original max element...

test case : no node , 1 node
step 1 : from root keep moving right till null ... got the max element
step 2 :
case 1: if left subtree(right subtree not possible) .. go to its root and
repeat step 1
case 2: if there is no left subtree then its parent (max node will always
be the right child of parent)

Node pick = TreeTop;
Node parent = null;
while (pick.right != null)
{
    parent = pick;
    pick = pick.right;
}
if parent == null
{
    pick = pick.left;
    while (pick.right != null)
    {
        pick = pick.right;
    }
    return pick;
}
else
{
    if pick.left == null
    {
        return parent;
    }
    else
    {
        pick = pick.left;
        while (pick.right != null)
        {
            pick = pick.right;
        }
    }
}

Ambrose, your code is not going to work. Re-walk your code and you will understand why.

If we can find the largest node, then all we need to do is while traversing the tree everytime we find a value > than largest then assign the original largest to 2nd largest and assign the value to the largest.

wtf
what the hell is a ordered binary tree? can someone explain with an example