algorithm - Question on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes? -

tree node contains 3 pointers *left, *right , *successor .

struct node{      int data;      struct node *left;      struct node *right;      struct node *successor;  };                   /  \       b    c      / \  / \     d   e f  g 

inorder traversal: dbeafcg *note:* inorder successors f,c , g.

  **function prototype:** void  fillsuccessornodes( struct node *root); 

tree's root node given , need fill successor pointer nodes.

case 1) of successor pointers may null . case have fill pointer immediate inorder successor.

example: if a->successor == null, fill a->successor = f

case 2) of successor pointers may points correct successors. case no need modify successor pointers.

example: 1) a->successor = f valid

     2) a->successor = c valid       3) a-successor = g valid  . these 3 cases no need modify successor pointer since these pointing correct successor nodes.   

case 3) of successor pointers not null these pointers pointing invalid successors i.e inorder successor or garbage value. case have fill these nodes immediate successor nodes.

example:

     1) a->successor = b invalid since b not successor node , have correct a->successor = f.       2) a->successor = 0x23237463478 invalid since pointing garbage value. we have correct a->successor = f.  

1) interviewer asked me time efficient solution in o(n) time complexity. space allowed. 2) gave hint i.e can use hashing.

if know solution problem, please let me know .

the question , hint seem misleading me. since have check nodes anyway check if successors invalid, , since have compute successor know invalid means, might use standard o(n) inorder traversal, e.g.:

#include <utility> using namespace std;  typedef pair<node*, node*> node_pair;  node_pair setinordersuccessors(node* root) {     node_pair result(root, root);      if (root->left) {         const node_pair pair = setinordersuccessors(root->left);         result.first = pair.first;         pair.second->successor = root;     }      if (root->right) {         const node_pair pair = setinordersuccessors(root->right);         result.second = pair.second;         root->successor = pair.first;     }      return result; }  void  fillsuccessornodes(node *root) {     const node_pair pair = setinordersuccessors(root);     pair.second->successor = 0; }