Find next right node of a given key | GeeksforGeeks

Find next right node of a given key | GeeksforGeeks
Given a Binary tree and a key in the binary tree, find the node right to the given key. If there is no node on right side, then return NULL. Expected time complexity is O(n) where n is the number of nodes in the given binary tree.
The idea is to do level order traversal of given Binary Tree. When we find the given key, we just check if the next node in level order traversal is of same level, if yes, we return the next node, otherwise return NULL.

node* nextRight(node *root, int k)

{

    // Base Case

    if (root == NULL)

        return 0;

    // Create an empty queue for level order tarversal

    queue<node *> qn; // A queue to store node addresses

    queue<int> ql;   // Another queue to store node levels

    int level = 0;  // Initialize level as 0

    // Enqueue Root and its level

    qn.push(root);

    ql.push(level);

    // A standard BFS loop

    while (qn.size())

    {

        // dequeue an node from qn and its level from ql

        node *node = qn.front();

        level = ql.front();

        qn.pop();

        ql.pop();

        // If the dequeued node has the given key k

        if (node->key == k)

        {

            // If there are no more items in queue or given node is

            // the rightmost node of its level, then return NULL

            if (ql.size() == 0 || ql.front() != level)

               return NULL;

            // Otherwise return next node from queue of nodes

            return qn.front();

        }

        // Standard BFS steps: enqueue children of this node

        if (node->left != NULL)

        {

            qn.push(node->left);

            ql.push(level+1);

        }

        if (node->right != NULL)

        {

            qn.push(node->right);

            ql.push(level+1);

        }

    }

    // We reach here if given key x doesn't exist in tree

    return NULL;

}

Read full article from Find next right node of a given key | GeeksforGeeks