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.
Read full article from 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;}