Given a binary tree where each node has one extra pointer *next*, set next pointer to inorder successor for all nodes in the binary tree.

Inorder Successor of node 4 is 2

Inorder Successor of node 2 is 1

Inorder Successor of node 1 is 7

Inorder Successor of node 7 is 5

Inorder Successor of node 5 is 8

Inorder Successor of node 8 is 3

Inorder Successor of node 3 is 6

Inorder Successor of node 6 is null

The idea is to perform in-order traversal of the tree and maintain previously processed node for every tree node. Then, for every node in in-order traversal, we set its next node to previously visited node. This is demonstrated below in C++ –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right, *next; }; // Function to set next pointer of all nodes in a binary tree // curr -> current node // prev -> previous processed node (Passed by reference) void setNextNode(Node* curr, Node* &prev) { // return if tree is empty if (curr == nullptr) return; // recurse for left subtree setNextNode(curr->left, prev); // set previous node next pointer to current node if (prev != nullptr) prev->next = curr; // update previous node to current node prev = curr; // recurse for right subtree setNextNode(curr->right, prev); } // Function to print inorder Successor of all nodes of // binary tree using next pointer void inorderSuccessor(Node* curr) { Node* prev = nullptr; // set next pointer of all nodes setNextNode(curr, prev); // go to leftmost node curr = curr->left->left; // print inorder Successor of all nodes while (curr->next) { cout << "Inorder Successor of node " << curr->data << " is " << curr->next->data << endl; curr = curr->next; } } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

please do it in JAVA

and also put all the programs in python.