Given a binary tree and a node in it, write an efficient algorithm to find its next node in same level as given node.

For example, consider below binary tree

Next node of 2 is 3

Next node of 5 is 6

Next node of 7 is 8

Next node of 8 is null

Simple solution would be to perform level order traversal of the tree. We can modify level order traversal to maintain level number of each node. Then if the given node is found, we return its immediate right node which is present at the same level.

**C++ implementation –**

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 51 52 53 54 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Function to find next node of given node in the same level // in given binary tree Node* findRightNode(Node* root, int val) { // return null if tree is empty if (root == nullptr) return nullptr; // create an empty queue and enqueue root node list<Node*> queue; queue.push_back(root); // pointer to store current node Node* front = nullptr; // run till queue is not empty while (!queue.empty()) { // calculate number of nodes in current level int size = queue.size(); // process every node of current level and enqueue their // non-empty left and right child to queue while (size--) { front = queue.front(); queue.pop_front(); // if desired node is found, return its next right node if (front->key == val) { // if next right node doesn't exists, return null if (queue.empty()) return nullptr; return queue.front(); } if (front->left) queue.push_back(front->left); if (front->right) queue.push_back(front->right); } } return nullptr; } |

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

We can also solve this problem by using constant auxiliary space and in linear time. The idea is to traverse the tree in preorder fashion and search for the given node. Once the given node is found, we mark its level number. Then the first node encountered at same level is the next right node.

**C++ implementation –**

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 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Function to find next node for given node in same level in a binary // tree by using pre-order traversal Node* findRightNode(Node* root, int value, int level, int &value_level) { // return null if tree is empty if (root == nullptr) return nullptr; // if desired node is found, set value_level to current level if (root->key == value) { value_level = level; return nullptr; } // if value_level is already set, then current node is next right node else if (value_level) { if (level == value_level) return root; } // recurse for left subtree by increasing level by 1 Node* left = findRightNode(root->left, value, level + 1, value_level); // if node is found in left subtree, return it if (left) return left; // recurse for right subtree by increasing level by 1 return findRightNode(root->right, value, level + 1, value_level); } // Function to find next node of given node in the same level // in given binary tree Node* findRightNode(Node* root, int value) { int value_level = 0; return findRightNode(root, value, 1, value_level); } |

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

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

## Leave a Reply

In the first algorithm instead of condition if (queue.empty()) should be if (size == 0). We should check if there are no nodes on current level. For example, next node of 3 is null not 4. Thank you.