CareerCup

Use hash_map to get O(n) algorithm:

#include<vector>
#include<hash_map>
#include<iostream>
#include<cstring>
using namespace std;
using namespace stdext;

struct node
{
	int data;
	struct node *left;
	struct node *right;
	struct node *successor;
};

void InorderTraversal( node *cur_node, vector<node*> &v, hash_map<node*, int> &hmap )
{
	if( cur_node )
	{
		if( cur_node->left )
		{
			InorderTraversal( cur_node->left, v, hmap );
		}
		v.push_back(cur_node);
		hmap[cur_node] = v.size() - 1;
		if( cur_node->right )
		{
			InorderTraversal( cur_node->right, v, hmap );
		}
	}
}

void FindSuccessorNodes( node *&root )
{
	vector<node*> v;
	hash_map<node*, int> hmap;
	InorderTraversal( root, v, hmap );
	if( v.size()>0 )
	{
		for( int i=0; i<v.size(); i++ )
		{
			if( i<v.size()-1 )
			{
				if( v[i]->successor==NULL )
				{
					v[i]->successor = v[i+1];
				}
				else if( hmap.count(v[i]->successor)>0 )
				{
					if( hmap[v[i]->successor<=hmap[v[i]] )
					{
						v[i]->successor = v[i+1];
					}
				}
				else
				{
					v[i]->successor = v[i+1];
				}
			}
			else
			{
				if( v[i]->successor )
				{
					v[i]->successor = NULL;
				}
			}
		}
	}
}

public class FindInorderSuccesor {
	
	static TreeNode succesor = null;
        static Set<TreeNode> set = new HashSet<TreeNode>();
	/*
	 * Traverse node from by right - center - left
	 * Assign value from buffer as succesor 
	 */
	public static void doFind(TreeNode root) {
		
		if(root.right  != null) {
			doFind(root.right);
		}
		//Assign succesor from buffer
		if(succesor == null) {
			root.succesor = succesor;
		} else {
			if(!set.contains(root.succesor)) {
				root.succesor =  succesor;
			}
		}
		
		set.add(root);
		succesor = root;
		
		if(root.left != null) {
			doFind(root.left);
		}
		
	}

I don't know why she said hashing but my solution would be.

- Do an inorder traversal and store the node information in a linear array. In your example the array will be D B E A F C G node pointers. O(n)
- Update the successor pointers using the array. Obviously successor for each node is the next element after itself in the array. O(n)
- So it will be O(2n) which O(n).

@rayeden
What about if all the successor are already pointed to G

Will you still be able to do it in O(n) using pointer approach.

map<node*,int>m;
node *a[n],i=0;
void inorder1(node *root){
inorder(root->left);
m[root]=0// a check to see the garbage pointer.
inorder(root->right);
}

void inorder(node *root){
inorder(root->left);
if(root->successor==NULL || m.find(root->successor)==m.end() || m[root->successor]==1)
root->successor=a[i+1];
m[root]=1;

inorder(root->right);



}

In first traversal store each node in an array and initialize mao with key as node and initialize it to zero means all are non visited.

In second traversal

If successor is null or pointing to garbage (cab be checked as if it pointing to some node of tree than the pointed node must be present as key) or pointing to a node which is already visited (means the pointed node comes before the current node in inorder traversal) than we need to set the successor node.

After that just mark the current node as visited.

While doing in order traversal populate the map with node and its in order position. So after the traversal the map will be like the following for the tree mentioned in question
D - 1, B - 2, E - 3, A - 4, F - 5, C - 6, G - 7.
Now iterate through the map.
For each node get the successor pointer and lookup in the map.
Case a: A value greater that the current value returned . The successor pointer is proper.
Case b: Null value is returned - garbage
Case c: A value less than the current value is returned.
For case b and c, set the successor pointer to next element in the map.
Same applies if the successor pointer is null.

inorder(root,succ)
{
ret_r = root;
ret_l = root;
if( root->left != NULL)
ret_l = inorder(root->left,root);
if(root->right != NULL)
ret_r = inorder(root->right,root);
if(ret_r != NULL)
root->succ = ret_r;
else
root->succ = parent;
return ret_l;
}

First call : inorder(root,NULL);
The above function will initialize all inorder successors in the tree !!!!!

inorder(root,succ)
{
ret_r = root;
ret_l = root;
if( root->left != NULL)
ret_l = inorder(root->left,root);
if(root->right != NULL)
ret_r = inorder(root->right,root);
if(ret_r != NULL)
root->succ = ret_r;
else
root->succ = parent;
return ret_l;
}

First call : inorder(root,NULL);
The above function will initialize all inorder successors in the tree !!!!!

Pls discard previous ans. ther wer typing mistakes........
norder(root,succ)
{
ret_r = root;
ret_l = root;
if( root->left != NULL)
ret_l = inorder(root->left,root);
if(root->right != NULL)
ret_r = inorder(root->right,succ);
if(ret_r != NULL)
root->succ = ret_r;
else
root->succ = succ;
return ret_l;
}

First call : inorder(root,NULL);
The above function will initialize all inorder successors in the tree !!!!!

norder(root,succ)
{
ret_r = NULL;
ret_l = root;
if( root->left != NULL)
ret_l = inorder(root->left,root);
if(root->right != NULL)
ret_r = inorder(root->right,succ);
if(ret_r != NULL)
root->succ = ret_r;
else
root->succ = succ;
return ret_l;
}

Below Solution was tested and it woks for all special cases.

Static prev = null;

static void setSuccesor(Node n) {

if (n != null) {
setSuccesor(n.left);

if (prev != null)
prev.sucessor = n;
prev = n;
setSuccesor(n.right);
}
}

Belo Solutionwas tested and works for all special cases.
static void setSuccesor(Node n) {

if (n != null) {
setSuccesor(n.left);
if (prev != null)
prev.sucessor = n;
prev = n;
setSuccesor(n.right);
}
}

Correct me if I am wrong.

Node *pSucc = NULL;
void SetSucc(Node *pRoot)
{
if (pRoot == NULL) return;

SetSucc(pRoot->right);

pRoot->succ = pSucc;
pSucc = pRoot;

SetSucc(pRoot->left);
}

Just traversing in reverse order RIGHT, ROOT, LEFT and storing successor in global.
}

@Araynium...u need to make changes to ur code to support cases 1,2,3...and r u sure whether u'll get correct in-order successors for all nodes..according to ur code i see some leaf nodes get their parent or someother node as successors which should be just null..

guys..plz clarify this...as posted by Rayden..is it true tht successor for each node is the next element after itself in the in-order list of elements...i guess it will not work for all the elements..

If we maintain an array of nodes DBEAFCG and a hash D:0, B:1 ... G:7 we can achieve all the requirements in O(N). Let's call the first array above as arr_1 and the second hash hash_2.

Algorithm:

1. Set cntr = 0;

2. In an inorder traversal starting with D do the following recursively:

a) Check if successor of this node is null - if it is - set it to arr_1[++cntr]; If not null go to step b)

b) Check if the already populated successor if present in hash_2, if not - set it to arr_1[++cntr] else go to step c)

c) Get the index of already populated successor from hash_2. If this index is greater than index of current node - do nothing else go to step d)

d) Set the successor to arr_1[++cntr]

Please let me know the inefficiencies related to this solution - One inefficiency is extra space but If we had to do this in O(n) I guess we need readily saved the immediate next successor (which we do in arr_1) and index of all other nodes to check if a node is before or after this node (which we do in hash_2).


*Edit*
Here is some code:

public class FindSuccessor {
    private Map<TreeNode,Integer> hash_2 = new HashMap<>();
    private TreeNode[] arr_1;
    private int ctr = 0;
    
    public void doFind(TreeNode root) {
        if(root.getLeft()!=null) doFind(root.getLeft());
        assignSuccessor(root);
        if(root.getRight()!=null) doFind(root.getRight());
    }

    private void assignSuccessor(TreeNode<String> root) {
        if(root.getSucc() == null) {
            setNextAsSucc(root);
        } else {
            TreeNode<String> succ = root.getSucc();
            if(!hashInorderNodes.containsKey(succ)) {
                setNextAsSucc(root);
            } else {
                if(hashInorderNodes.get(succ) < hashInorderNodes.get(root)) {
                    setNextAsSucc(root);
                } else {
                    ++ctr;
                }
            }
        }
    }

    private void setNextAsSucc(TreeNode root) {
        try {
            root.setSucc(arr_1[++ctr]);
        } catch(ArrayIndexOutOfBoundsException a) {
            root.setSucc(null); // not required becuase null by default but here for readibility
        }
    }
}