CareerCup

I think having duplicate values wouldn't change the algorithm for finding successor without duplicate values.

#include <iostream>
#include <vector>
using namespace std;

class TreeNode
{
    public:
        TreeNode(int _v, TreeNode * _left, TreeNode * _right)
        {
            v = _v;
            left = _left;
            right = _right;
        }
        int v;
        TreeNode * left;
        TreeNode * right;
};

class BST
{
    public:
        BST()
        {
            root = NULL;
        }
        BST(int * a, int n);
        ~BST();
        TreeNode * Insert(int v);
        TreeNode * Search(int v);
        TreeNode * Successor(TreeNode * node);
        void Print();
        bool Find(TreeNode * node, vector<TreeNode* >& ancestors);
    private:
        void Release(TreeNode *node);
        void Print(TreeNode * node);
        TreeNode * root;
};


bool BST::Find(TreeNode * node, vector<TreeNode*>& ancestors)
{
    if (node == NULL)
        return false;
    int v = node->v;
    ancestors.clear();
    if (root == NULL)
        return false;
    
    TreeNode * cur = root;
    while (cur != NULL)
    {
        if (v < cur->v)
        {
            ancestors.push_back(cur);
            cur = cur->left;
            continue;
        }
        if (v > cur->v)
        {
            ancestors.push_back(cur);
            cur = cur->right;
            continue;
        }
        // v == cur->v
        if (cur == node)
            break;
        ancestors.push_back(cur);
        cur = cur->right;
    }
    return cur == node;

}
TreeNode * BST::Search(int v)
{
    TreeNode * cur = root;
    while (cur != NULL && cur->v != v)
    {
        if (v < cur->v)
            cur = cur->left;
        else if (v > cur->v)
            cur = cur->right;
    }
    //cur == NULL or cur->v == v
    return cur;
}
TreeNode * BST::Successor(TreeNode * node)
{
    TreeNode * successor = NULL;
    if (node == NULL)
        return NULL;
    // if node has right child
    // then successor is its leftmost descendent
    if (node->right != NULL)
    {
        successor = node->right;
        TreeNode * cur = node->right->left;
        while (cur != NULL)
        {
            successor = cur;
            cur = cur->left;
        }
        return successor;
    }

    //if node has no right child
    vector<TreeNode *> ancestor;
    bool bSuc = Find(node, ancestor);
    if (!bSuc)
        return NULL;
    
    ancestor.push_back(node);
    int n = ancestor.size();
    for (int i = n - 2; i >= 0; i--)
    {
        if (ancestor[i]->left == ancestor[i + 1])
        {
            successor = ancestor[i];
            break;
        }
    }
    return successor;
}
BST::BST(int *a, int n)
{
    root = NULL;
    for (int i = 0; i < n; i++)
    {
        Insert(a[i]);
    }
}
BST::~BST()
{
    Release(root);
}
void BST::Release(TreeNode * node)
{
    if (node == NULL)
        return;

    Release(node->left);
    Release(node->right);
    delete node;
}
/*
 left: less than
 right: great than or equal to
 middle: equal to
*/
TreeNode * BST::Insert(int v)
{
    //if the tree is empty
    if (root == NULL)
    { 
        root = new TreeNode(v, NULL, NULL);
        return root;
    }
    TreeNode * parent = NULL;
    TreeNode * cur = root;
    while (cur != NULL)
    {
        if (v < cur->v)
        {
            parent = cur;
            cur = cur->left;
            continue;
        }

        if (v >= cur->v)
        {
            parent = cur;
            cur = cur->right;
            continue;
        }
    }

    //now cur is NULL, its parent is parent
    TreeNode * node = new TreeNode(v, NULL, NULL);
    if (v < parent->v)
        parent->left = node;
    if (v >= parent->v)
        parent->right = node;
    return node;
}
void BST::Print()
{
    Print(root);
}

void BST::Print(TreeNode * node)
{
    if (node == NULL)
        return;

    Print (node->left);
    cout << node->v << " ";
    Print (node->right);
}

int main(int argc, char ** argv)
{
    int a[] = {2, 4, 6, 7, 5, 9, 10, 9, 8, 8, 2};
    // 2 2 4 5 6 7 8 8 9 9 10
    BST tree(a, sizeof(a) / sizeof(int));
    tree.Print();
    cout << endl;
    
    TreeNode * node = tree.Search(2);
    
    while (node != NULL)
    {
        cout << node->v << " ";
        node = tree.Successor(node);
    }
    cout << endl;
    //TreeNode * sucNode = tree.Successor(node);
    //cout << sucNode->v << endl;

    
    return 0;
}

I think my solution works for no duplicates. It takes O(depth) time and O(1) space. The basic idea is to store the most possible succ till now, which means the node with a value bigger than target but smaller than all the nodes we have checked.
Here is the code, if you find any bugs plz comment. : )

public static TreeNode findSuccessor(TreeNode root, TreeNode target)
	{
		boolean found = false;
		TreeNode succ = null;
		
		while (root != null)
		{
			if (root == target)
			{
				found = true;
				root = root.right; 
			}
			else if (root.data > target.data)
			{
				succ = root;
				root = root.left;
			}
			else
				root = root.right;
		}
		
		return found? succ: null;
	}

FndSuccessor( givenNode *g) {
node *n;
n = g -> right;
if (n ->left == NULL) return n;
while(n-> left!= NULL) n = n->left;
return n;

In case of no successor found, returns the same number. O(n) in time and space.

public static int succ(Node n) {
	if (n==null) thow new NullPointerException();
	if (n.right==null) return n.data;
	Stack<Node> st = new Stack<Node>();
	int value = n.data;
	n = n.right;
	while ((n.left!=null)&&(n.data==value)) {
		st.push(n);
		n = n.left;
	}
	while (st.size()>0) {
		Node x = st.pop();
		int tmp = succ(x);
		if (tmp!=value) return tmp;
	}
	return value;
}

do inorder traversal until we get node which is greater than input node. Will work for the duplicate as well.

One solution is :-
display the tree in order, then search fro successor. requires O(n) space, O(n) time.

My idea is : use a hashtable.
Key : Value:
Node.Value Node.address

Do in-order traverse. At the same time, we store corresponding key and value pair into hashtable.

After that: we have a list L like 123455555(6)6677
We have known the address of that Node N, we want its successor.
We compare the address in L until we find it, then we return the next one.