Find next right node of a given key

Last Updated : 19 Jan, 2023

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.

For example, consider the following Binary Tree. Output for 2 is 6, output for 4 is 5. Output for 10, 6 and 5 is NULL.

                  10
                /    \
              2        6
            /   \        \ 
           8     4         5

Solution: 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.

C++

/* Program to find next right of a given key */
#include <iostream>
#include <queue>
using namespace std;
 
// A Binary Tree Node
struct node
{
    struct node *left, *right;
    int key;
};
 
// Method to find next right of given key k, it returns NULL if k is
// not present in tree or k is the rightmost node of its level
node* nextRight(node *root, int k)
{
    // Base Case
    if (root == NULL)
        return 0;
 
    // Create an empty queue for level order traversal
    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;
}
 
// Utility function to create a new tree node
node* newNode(int key)
{
    node *temp = new node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to test above functions
void test(node *root, int k)
{
    node *nr = nextRight(root, k);
    if (nr != NULL)
      cout << "Next Right of " << k << " is " << nr->key << endl;
    else
      cout << "No next right node found for " << k << endl;
}
 
// Driver program to test above functions
int main()
{
    // Let us create binary tree given in the above example
    node *root = newNode(10);
    root->left = newNode(2);
    root->right = newNode(6);
    root->right->right = newNode(5);
    root->left->left = newNode(8);
    root->left->right = newNode(4);
 
    test(root, 10);
    test(root, 2);
    test(root, 6);
    test(root, 5);
    test(root, 8);
    test(root, 4);
    return 0;
}

Java

// Java program to find next right of a given key
  
import java.util.LinkedList;
import java.util.Queue;
  
// A binary tree node
class Node 
{
    int data;
    Node left, right;
  
    Node(int item) 
    {
        data = item;
        left = right = null;
    }
}
  
class BinaryTree 
{
    Node root;
  
    // Method to find next right of given key k, it returns NULL if k is
    // not present in tree or k is the rightmost node of its level
    Node nextRight(Node first, int k) 
    {
        // Base Case
        if (first == null)
            return null;
  
        // Create an empty queue for level order traversal
        // A queue to store node addresses
        Queue<Node> qn = new LinkedList<Node>(); 
         
        // Another queue to store node levels
        Queue<Integer> ql = new LinkedList<Integer>();   
  
        int level = 0;  // Initialize level as 0
  
        // Enqueue Root and its level
        qn.add(first);
        ql.add(level);
  
        // A standard BFS loop
        while (qn.size() != 0) 
        {
            // dequeue an node from qn and its level from ql
            Node node = qn.peek();
            level = ql.peek();
            qn.remove();
            ql.remove();
  
            // If the dequeued node has the given key k
            if (node.data == 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.peek() != level)
                    return null;
  
                // Otherwise return next node from queue of nodes
                return qn.peek();
            }
  
            // Standard BFS steps: enqueue children of this node
            if (node.left != null) 
            {
                qn.add(node.left);
                ql.add(level + 1);
            }
            if (node.right != null) 
            {
                qn.add(node.right);
                ql.add(level + 1);
            }
        }
  
        // We reach here if given key x doesn't exist in tree
        return null;
    }
  
    // A utility function to test above functions
    void test(Node node, int k) 
    {
        Node nr = nextRight(root, k);
        if (nr != null)
            System.out.println("Next Right of " + k + " is " + nr.data);
        else
            System.out.println("No next right node found for " + k);
    }
  
    // Driver program to test above functions
    public static void main(String args[]) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(2);
        tree.root.right = new Node(6);
        tree.root.right.right = new Node(5);
        tree.root.left.left = new Node(8);
        tree.root.left.right = new Node(4);
  
        tree.test(tree.root, 10);
        tree.test(tree.root, 2);
        tree.test(tree.root, 6);
        tree.test(tree.root, 5);
        tree.test(tree.root, 8);
        tree.test(tree.root, 4);
  
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to find next right node of given key
 
# A Binary Tree Node
class Node:
     
    # Constructor to create a new node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
     
# Method to find next right of a given key k, it returns
# None if k is not present in tree or k is the rightmost
# node of its level
def nextRight(root, k):
 
    # Base Case
    if root is None:
        return 0
 
    # Create an empty queue for level order traversal
    qn =  [] # A queue to store node addresses
    q1 = [] # Another queue to store node levels
 
    level = 0
 
    # Enqueue root and its level
    qn.append(root)
    q1.append(level)
 
    # Standard BFS loop
    while(len(qn) > 0):
 
        # Dequeue an node from qn and its level from q1
        node = qn.pop(0)
        level = q1.pop(0)
 
        # 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 None
            if (len(q1) == 0 or q1[0] != level):
                return None
 
            # Otherwise return next node from queue of nodes
            return qn[0]
 
        # Standard BFS steps: enqueue children of this node
        if node.left is not None:
            qn.append(node.left)
            q1.append(level+1)
 
        if node.right is not None:
            qn.append(node.right)
            q1.append(level+1)
 
    # We reach here if given key x doesn't exist in tree
    return None
 
def test(root, k):
    nr = nextRight(root, k)
    if nr is not None:
        print ("Next Right of " + str(k) + " is " + str(nr.key))
    else:
        print ("No next right node found for " + str(k))
 
# Driver program to test above function
root = Node(10)
root.left = Node(2)
root.right = Node(6)
root.right.right = Node(5)
root.left.left = Node(8)
root.left.right = Node(4)
 
test(root, 10)
test(root, 2)
test(root, 6)
test(root, 5)
test(root, 8)
test(root, 4)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to find next right of a given key 
using System;
using System.Collections.Generic;
 
// A binary tree node 
public class Node 
{ 
    public int data; 
    public Node left, right; 
 
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 
 
public class BinaryTree 
{ 
    Node root; 
 
    // Method to find next right of given
    // key k, it returns NULL if k is 
    // not present in tree or k is the 
    // rightmost node of its level 
    Node nextRight(Node first, int k) 
    { 
        // Base Case 
        if (first == null) 
            return null; 
 
        // Create an empty queue for
        // level order traversal 
        // A queue to store node addresses 
        Queue<Node> qn = new Queue<Node>(); 
         
        // Another queue to store node levels 
        Queue<int> ql = new Queue<int>(); 
 
        int level = 0; // Initialize level as 0 
 
        // Enqueue Root and its level 
        qn.Enqueue(first); 
        ql.Enqueue(level); 
 
        // A standard BFS loop 
        while (qn.Count != 0) 
        { 
            // dequeue an node from 
            // qn and its level from ql 
            Node node = qn.Peek(); 
            level = ql.Peek(); 
            qn.Dequeue(); 
            ql.Dequeue(); 
 
            // If the dequeued node has the given key k 
            if (node.data == k) 
            { 
                // If there are no more items
                // in queue or given node is 
                // the rightmost node of its 
                // level, then return NULL 
                if (ql.Count == 0 || ql.Peek() != level) 
                    return null; 
 
                // Otherwise return next 
                // node from queue of nodes 
                return qn.Peek(); 
            } 
 
            // Standard BFS steps: enqueue
            // children of this node 
            if (node.left != null) 
            { 
                qn.Enqueue(node.left); 
                ql.Enqueue(level + 1); 
            } 
            if (node.right != null) 
            { 
                qn.Enqueue(node.right); 
                ql.Enqueue(level + 1); 
            } 
        } 
 
        // We reach here if given 
        // key x doesn't exist in tree 
        return null; 
    } 
 
    // A utility function to test above functions 
    void test(Node node, int k) 
    { 
        Node nr = nextRight(root, k); 
        if (nr != null) 
            Console.WriteLine("Next Right of " + 
                        k + " is " + nr.data); 
        else
            Console.WriteLine("No next right node found for " + k); 
    } 
 
    // Driver code 
    public static void Main(String []args) 
    { 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(10); 
        tree.root.left = new Node(2); 
        tree.root.right = new Node(6); 
        tree.root.right.right = new Node(5); 
        tree.root.left.left = new Node(8); 
        tree.root.left.right = new Node(4); 
 
        tree.test(tree.root, 10); 
        tree.test(tree.root, 2); 
        tree.test(tree.root, 6); 
        tree.test(tree.root, 5); 
        tree.test(tree.root, 8); 
        tree.test(tree.root, 4); 
    } 
} 
 
// This code has been contributed
// by 29AjayKumar

Javascript

<script>
 
// Javascript program to find next right of a given key
 
// A binary tree node
class Node
{
    constructor(item)
    {
        this.data = item;
        this.left = this.right = null;
    }
}
 
let root;
 
// Method to find next right of given key k,
// it returns NULL if k is not present in 
// tree or k is the rightmost node of its level
function nextRight(first, k)
{
     
    // Base Case
    if (first == null)
        return null;
 
    // Create an empty queue for level
    // order traversal. A queue to 
    // store node addresses
    let qn = [];
      
    // Another queue to store node levels
    let ql = [];
     
    // Initialize level as 0
    let level = 0;  
 
    // Enqueue Root and its level
    qn.push(first);
    ql.push(level);
 
    // A standard BFS loop
    while (qn.length != 0)
    {
         
        // dequeue an node from qn and its level from ql
        let node = qn[0];
        level = ql[0];
        qn.shift();
        ql.shift();
 
        // If the dequeued node has the given key k
        if (node.data == k)
        {
             
            // If there are no more items in queue 
            // or given node is the rightmost node 
            // of its level, then return NULL
            if (ql.length == 0 || ql[0] != level)
                return null;
 
            // Otherwise return next node 
            // from queue of nodes
            return qn[0];
        }
 
        // 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;
}
 
// A utility function to test above functions
function test(node, k)
{
    let nr = nextRight(root, k);
    if (nr != null)
        document.write("Next Right of " + k +
                       " is " + nr.data + "<br>");
    else
        document.write("No next right node found for " +
                       k + "<br>");
}
 
// Driver code
root = new Node(10);
root.left = new Node(2);
root.right = new Node(6);
root.right.right = new Node(5);
root.left.left = new Node(8);
root.left.right = new Node(4);
   
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
 
// This code is contributed by rag2127
 
</script>

Output

No next right node found for 10
Next Right of 2 is 6
No next right node found for 6
No next right node found for 5
Next Right of 8 is 4
Next Right of 4 is 5

Time Complexity: The above code is a simple BFS traversal code which visits every enqueue and dequeues a node at most once. Therefore, the time complexity is O(n) where n is the number of nodes in the given binary tree.
Auxiliary Space: O(n)

Efficient Approach :

The idea is to use the level order traversal of a binary tree discussed in the 2nd approach of this post.

If we do the level order traversal in the above fashion then while processing the nodes of a level we can check if it is the last element of that level or not. If it is not the last element of it’s level then there will definitely be an element next to it. See the below C++ code to understand the approach clearly.

Implementation:

C++

/* Program to find next right of a given key */
#include <iostream>
#include <queue>
using namespace std;
 
// A Binary Tree Node
struct node {
    struct node *left, *right;
    int key;
};
 
// Method to find next right of given key k, it returns NULL
// if k is not present in tree or k is the rightmost node of
// its level
node* nextRight(node* root, int key)
{
    // Base case
    if (root == NULL)
        return NULL;
 
    // variable to store the result
    node* res = NULL;
 
    // queue q to store the nodes of the tree
    queue<node*> q;
 
    // push the root in the queue
    q.push(root);
 
    // A modified BFS loop
    while (!q.empty()) {
        // Get the count of the elements in the queue, this
        // is also the count of elements present at the
        // current level
        int n = q.size();
        // loop through the elements of the current level
        for (int i = 0; i < n; i++) {
            // take out the front of the queue
            node* temp = q.front();
            q.pop();
            // if the key is found we check if there is any
            // element next to it and return the answer
            // accordingally
            if (temp->key == key) {
                if (i != n - 1)
                    return q.front();
                else
                    return NULL;
            }
            // while the current level elements are
            // processed we push their children into the
            // queue
            if (temp->left)
                q.push(temp->left);
            if (temp->right)
                q.push(temp->right);
        }
    }
    // If we reach here, it means the element was not found
    // and thus no next element will be there
    return NULL;
}
 
// Utility function to create a new tree node
node* newNode(int key)
{
    node* temp = new node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to test above functions
void test(node* root, int k)
{
    node* nr = nextRight(root, k);
    if (nr != NULL)
        cout << "Next Right of " << k << " is " << nr->key
             << endl;
    else
        cout << "No next right node found for " << k
             << endl;
}
 
// Driver program to test above functions
int main()
{
    // Let us create binary tree given in the above example
    node* root = newNode(10);
    root->left = newNode(2);
    root->right = newNode(6);
    root->right->right = newNode(5);
    root->left->left = newNode(8);
    root->left->right = newNode(4);
 
    test(root, 10);
    test(root, 2);
    test(root, 6);
    test(root, 5);
    test(root, 8);
    test(root, 4);
    return 0;
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Java

// Java program to find next right of a given key
import java.util.LinkedList;
import java.util.Queue;
 
// A binary tree node
class Node {
    int data;
    Node left, right;
 
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
    Node root;
 
    // Method to find next right of given key k, it returns
    // NULL if k is not present in tree or k is the
    // rightmost node of its level
    Node nextRight(Node first, int k)
    {
        // Base Case
        if (first == null)
            return null;
 
        // Create an empty queue for level order traversal
        // A queue to store node addresses
        Node res = null;
        Queue<Node> q = new LinkedList<Node>();
 
        // Enqueue Root and its level
        q.add(first);
 
        // A standard BFS loop
        while (q.size() != 0) {
            // Get the count of the elements in the queue,
            // this
            // is also the count of elements present at the
            // current level
            int n = q.size();
            // loop through the elements of the current
            // level
            for (int i = 0; i < n; i++) {
                Node temp = q.peek();
                q.remove();
                // if the key is found we check if there is
                // any
                // element next to it and return the answer
                // accordingally
                if (temp.data == k) {
                    if (i != n - 1) {
                        return q.peek();
                    }
                    else
                        return null;
                }
                // while the current level elements are
                // processed we push their children into the
                // queue
                if (temp.left != null)
                    q.add(temp.left);
                if (temp.right != null)
                    q.add(temp.right);
            }
        }
 
        // We reach here if given key x doesn't exist in
        // tree
        return null;
    }
 
    // A utility function to test above functions
    void test(Node node, int k)
    {
        Node nr = nextRight(root, k);
        if (nr != null)
            System.out.println("Next Right of " + k + " is "
                               + nr.data);
        else
            System.out.println(
                "No next right node found for " + k);
    }
 
    // Driver program to test above functions
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(2);
        tree.root.right = new Node(6);
        tree.root.right.right = new Node(5);
        tree.root.left.left = new Node(8);
        tree.root.left.right = new Node(4);
 
        tree.test(tree.root, 10);
        tree.test(tree.root, 2);
        tree.test(tree.root, 6);
        tree.test(tree.root, 5);
        tree.test(tree.root, 8);
        tree.test(tree.root, 4);
    }
}
 
// This code is contributed by garg28harsh.

C#

// C# program to find next right of a given key
 
using System;
using System.Collections;
 
// A binary tree node
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
// This Code is contributed by karandeep1234
public class BinaryTree {
    public Node root;
 
    // Method to find next right of given key k, it returns
    // NULL if k is not present in tree or k is the
    // rightmost node of its level
    public Node nextRight(Node first, int k)
    {
        // Base Case
        if (first == null)
            return null;
 
        // Create an empty queue for level order traversal
        // A queue to store node addresses
        // Node res = null;
        Queue q = new Queue();
 
        // Enqueue Root and its level
        q.Enqueue(first);
 
        // A standard BFS loop
        while (q.Count != 0) {
            // Get the count of the elements in the queue,
            // this
            // is also the count of elements present at the
            // current level
            int n = q.Count;
            // loop through the elements of the current
            // level
            for (int i = 0; i < n; i++) {
                Node temp = (Node)q.Peek();
                q.Dequeue();
                // if the key is found we check if there is
                // any
                // element next to it and return the answer
                // accordingally
                if (temp.data == k) {
                    if (i != n - 1) {
                        return (Node)q.Peek();
                    }
                    else
                        return null;
                }
                // while the current level elements are
                // processed we push their children into the
                // queue
                if (temp.left != null)
                    q.Enqueue(temp.left);
                if (temp.right != null)
                    q.Enqueue(temp.right);
            }
        }
 
        // We reach here if given key x doesn't exist in
        // tree
        return null;
    }
 
    // A utility function to test above functions
    void test(Node node, int k)
    {
        Node nr = nextRight(root, k);
        if (nr != null)
            Console.WriteLine("Next Right of " + k + " is "
                              + nr.data);
        else
            Console.WriteLine(
                "No next right node found for " + k);
    }
 
    // Driver program to test above functions
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(2);
        tree.root.right = new Node(6);
        tree.root.right.right = new Node(5);
        tree.root.left.left = new Node(8);
        tree.root.left.right = new Node(4);
 
        tree.test(tree.root, 10);
        tree.test(tree.root, 2);
        tree.test(tree.root, 6);
        tree.test(tree.root, 5);
        tree.test(tree.root, 8);
        tree.test(tree.root, 4);
    }
}

Javascript

// JavaScript program to find next right of a given key
 
class Node{
    constructor(item){
        this.data = item;
        this.left = this.right = null;
    }
}
 
var root;
 
// Method to find next right of given key k, it returns
// NULL if k is not present in tree or k is the
// rightmost node of its level
function nextRight(first, k)
{
 
    // Base Case
    if (first == null)
        return null;
 
    // Create an empty queue for level order traversal
    // A queue to store node addresses
    var res = null;
    var q = [];
 
    // Enqueue Root and its level
    q.push(first);
 
    // A standard BFS loop
    while (q.length != 0)
    {
        // Get the count of the elements in the queue,
        // this
        // is also the count of elements present at the
        // current level
        var n = q.length;
         
        // loop through the elements of the current
        // level
        for(let i=0;i<n;i++){
            let temp = q[0];
            q.shift();
 
            // if the key is found we check if there is
            // any
            // element next to it and return the answer
            // accordingally
            if (temp.data == k)
            {
                if (i != n -1 ){
                    return q[0];
                   }
                else{
                    return null;
                }
            }
 
            // while the current level elements are
            // processed we push their children into the
            // queue
            if (temp.left != null)
            {
                q.push(temp.left);
            }
            if (temp.right != null)
            {
                q.push(temp.right);
            }
        }
         
    }
 
    // We reach here if given key
    // x doesn't exist in tree
    return null;
}
 
// A utility function to test above functions
function test(node, k)
{
    let nr = nextRight(root, k);
    if (nr != null)
        console.log("Next Right of " + k +
                       " is " + nr.data + "<br>");
    else
        console.log("No next right node found for " +
                       k + "<br>");
}
 
root = new Node(10);
root.left = new Node(2);
root.right = new Node(6);
root.right.right = new Node(5);
root.left.left = new Node(8);
root.left.right = new Node(4);
 
test(root, 10);
test(root, 2);
test(root, 6);
test(root, 5);
test(root, 8);
test(root, 4);
 
// This code is contributed by lokeshmvs21.

Python3

# Python program to find next right of a given key
 
class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None
 
root = None
 
# Method to find next right of given key k, it returns
# None if k is not present in tree or k is the
# rightmost node of its level
def nextRight(first, k):
 
    # Base Case
    if first is None:
        return None
 
    # Create an empty queue for level order traversal
    # A queue to store node addresses
    res = None
    q = []
 
    # Enqueue Root and its level
    q.append(first)
 
    # A standard BFS loop
    while len(q) != 0:
        # Get the count of the elements in the queue,
        # this
        # is also the count of elements present at the
        # current level
        n = len(q)
 
        # loop through the elements of the current
        # level
        for i in range(n):
            temp = q[0]
            q.pop(0)
 
            # if the key is found we check if there is
            # any
            # element next to it and return the answer
            # accordingally
            if temp.data == k:
                if i != n - 1:
                    return q[0]
                else:
                    return None
 
            # while the current level elements are
            # processed we push their children into the
            # queue
            if temp.left is not None:
                q.append(temp.left)
            if temp.right is not None:
                q.append(temp.right)
 
    # We reach here if given key
    # x doesn't exist in tree
    return None
 
# A utility function to test above functions
def test(node, k):
    nr = nextRight(root, k)
    if nr is not None:
        print("Next Right of " + str(k) +
              " is " + str(nr.data))
    else:
        print("No next right node found for " +
              str(k))
 
root = Node(10)
root.left = Node(2)
root.right = Node(6)
root.right.right = Node(5)
root.left.left = Node(8)
root.left.right = Node(4)
 
test(root, 10)
test(root, 2)
test(root, 6)
test(root, 5)
test(root, 8)
test(root, 4)
# contributed by akashish__

Output

No next right node found for 10
Next Right of 2 is 6
No next right node found for 6
No next right node found for 5
Next Right of 8 is 4
Next Right of 4 is 5

Time Complexity: O(N), Although we are using nested loops but if you observe we are just traversing every element of the tree just once.
Auxiliary Space: O(B), Here B is the breadth of the tree and the extra space is used by the elements stored in the queue.
The extra space used in this approach is less than the previous approach as we are using only a single queue.

This approach was contributed by Abhijeet Kumar.

Exercise: Write a function to find left node of a given node. If there is no node on the left side, then return NULL.

GeeksforGeeks

Improve

Previous Article

Print all nodes between two given levels in Binary Tree

Minimum steps to reach target by a Knight | Set 1

Similar Reads

Find next right node of a given key | Set 2

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.For example, consider the following Binary Tree. Output for 2 is 6, output for 4 is 5. Output for 10, 6 and 5 is NULL. 1

Replace every node of a Linked list with the next greater element on right side

Given a linked list, the task is to find the Next Greater Element for every node of the linked list. Note: For nodes with no next greater element, store -1 in the result. Examples: Input: linked list = [2, 1, 5] Output: [5, 5, -1] Input: linked list = [2, 7, 4, 3, 5] Output: [7, -1, 5, 5, -1] Approach: To solve the problem mentioned above the main

Find next Smaller of next Greater in an array

Given array of integer, find the next smaller of next greater element of every element in array. Note : Elements for which no greater element exists or no smaller of greater element exist, print -1. Examples: Input : arr[] = {5, 1, 9, 2, 5, 1, 7} Output: 2 2 -1 1 -1 -1 -1 Explanation : Next Greater -> Right Smaller 5 -> 9 9 -> 2 1 -> 9

Find the next non-zero Array element to the right of each array element

Given an array arr[] of N integers, the task is to find the next non-zero array element to the right of every array element. If there doesn't exist any non-zero element, then print that element itself. Examples: Input: arr[] = {1, 2, 0}Output: {2, 2, 0}Explanation:For each array element the next non-zero elements are:arr[0] = 1 -> 2arr[1] = 2 -

Count of Array elements greater than all elements on its left and next K elements on its right

Given an array arr[], the task is to print the number of elements which are greater than all the elements on its left as well as greater than the next K elements on its right. Examples: Input: arr[] = { 4, 2, 3, 6, 4, 3, 2}, K = 2 Output: 2 Explanation: arr[0](= 4): arr[0] is the 1st element in the array and greater than its next K(= 2) elements {2

How to implement decrease key or change key in Binary Search Tree?

Given a Binary Search Tree, write a function that takes the following three as arguments: Root of tree Old key value New Key Value The function should change old key value to new key value. The function may assume that old key-value always exists in Binary Search Tree. Example: Input: Root of below tree 50 / \ 30 70 / \ / \ 20 40 60 80 Old key valu

Store duplicate keys-values pair and sort the key-value pair by key

Given N key-value pairs that contain duplicate keys and values, the task is to store these pairs and sort the pairs by key. Examples: Input : N : 10 Keys : 5 1 4 6 8 0 6 6 5 5 values: 0 1 2 3 4 5 6 7 8 9 Output : Keys : 0 1 4 5 5 5 6 6 6 8 values: 5 1 2 0 8 9 3 6 7 4 Explanation: We have given 10 key, value pairs which contain duplicate keys and va

Convert left-right representation of a binary tree to down-right

Left-Right representation of a binary tree is standard representation where every node has a pointer to left child and another pointer to right child.Down-Right representation is an alternate representation where every node has a pointer to left (or first) child and another pointer to next sibling. So siblings at every level are connected from left

Count of possible paths from top left to bottom right of a M x N matrix by moving right, down or diagonally

Given 2 integers M and N, the task is to find the count of all the possible paths from top left to the bottom right of an M x N matrix with the constraints that from each cell you can either move only to right or down or diagonally Examples: Input: M = 3, N = 3Output: 13Explanation: There are 13 paths as follows: VVHH, VHVH, HVVH, DVH, VDH, VHHV, H

Print a matrix in alternate manner (left to right then right to left)

Given a 2D array, the task is to print the 2D in alternate manner (First row from left to right, then from right to left, and so on). Examples: Input : arr[][2] = {{1, 2} {2, 3}}; Output : 1 2 3 2 Input :arr[][3] = { { 7 , 2 , 3 }, { 2 , 3 , 4 }, { 5 , 6 , 1 }}; Output : 7 2 3 4 3 2 5 6 1 The solution of this problem is that run two loops and print

Article Tags :

Practice Tags :