Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement 
1.2.
Sample example 
2.
Recursive Approach 
2.1.
Steps of Algorithm 
2.2.
Implementation in C++
2.3.
Implementation in Java 
2.4.
Complexity analysis
3.
Frequently Asked Questions
3.1.
What exactly is a leaf node?
3.2.
What is a binary search tree?
3.3.
What do you know about an AVL tree?
4.
Conclusion
Last Updated: Mar 27, 2024

Reverse a path in BST using queue

Author Shivani Singh
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Here in this blog, we are asked to see various approaches to reverse a path in a binary search tree using a queue. We already are familiar with the concept of the trees and binary search tree and also with the queue data structures. So, let's dig a little deeper into this blog.

Problem statement 

In this problem, we are provided a binary search tree and we are asked to reverse its path around a node. Let us understand the problem statement with the help of an example. We need to keep in mind that for the binary search tree, the left node is smaller than the root node and the right node is larger than the root node. I.e left node<root node<right node.

Source: binary search tree

Sample example 

In the above diagram, we can clearly understand that we are given a binary search tree and a target node. And we have to reverse the path from the root node to the given target node. In the diagram given the inorder before reversing: 20 30 40 50 60 70 80

And inorder after reversing : 20 30 40 80 60 70 50

Recursive Approach 

This approach is very simple to implement and straightforward. Because reversing a path from the root to the target node is similar to reversing all the node elements present on the path from the root to the target node. For example, if the path contains 1->2->3->4 from the root node to that target node. Then after reversing the path will become 4->3->2->1. In this recursive approach, we will enqueue/push all the values of nodes in the path from the root to the given target node and then replace the existing current node with the element at the front of the queue.

Source: recursive function

Let us see its algorithm. 

Steps of Algorithm 

Step 1: If the root is null, return null.

Step 2: if the root value is equal to the target, push the root into the queue and replace the root value with the queue’s front. Dequeue the element in front of the queue 

Step 3: If the root value is less than the target, push it to the queue, call reversePathBST recursively for the root left child, and replace the root value with the element at the front of the queue. And remove the element at the top of the

Step 4: And if the value is greater push the root's value to the queue, call reversePathBST recursively for the root's right child, and then replace the root's value with the element at the front of the queue. And remove the element at the top of the queue.

 Let us see the implementation of this approach in the next section of this blog.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
struct node 
{
     int key;
     struct node * left, * right;
};
struct node * newNode(int item) 
{
     struct node * temp = new node;
     temp -> key = item;
     temp -> left = temp -> right = NULL;
     return temp;
}
void inorder_tree(struct node * root) 
{
     if (root != NULL) 
     {
          inorder_tree(root -> left);
          cout << root -> key << " ";
          inorder_tree(root -> right);
     }
}
void Reverse_tree(struct node ** node, int & key, queue < int > & q1) 
{
       if (node == NULL) //If the tree is empty then
             return;
       if (( * node) -> key == key) 
       {     // if we find the key
             q1.push(( * node) -> key); // we push it into our queue
             ( * node) -> key = q1.front(); // we change the first queue element with current
             q1.pop(); // we pop the first element
       } 
       else if (key < ( * node) -> key) 
       {      // if key is less than current node's value
              q1.push(( * node) -> key);
              Reverse_tree( & ( * node) -> left, key, q1); //recursive call
              ( * node) -> key = q1.front();
              q1.pop();
       } 
       else if (key > ( * node) -> key)
       {      // if key greater than node key then
              q1.push(( * node) -> key);
              Reverse_tree( & ( * node) -> right, key, q1); //recursice call
              ( * node) -> key = q1.front();
              q1.pop();
       }
       return;
}
struct node * insert_treenode(struct node * node, // function to insert node nodes in our BST
  int key) 
{
      if (node == NULL)
           return newNode(key); // if tree is empty we return a new node
      if (key < node -> key) // else we push that in our tree
           node -> left = insert_treenode(node -> left, key);
      else if (key > node -> key)
           node -> right = insert_treenode(node -> right, key);
      return node; // returning the node
}
int main() 
{
      struct node * root = NULL;
      queue < int > q1;
      int target = 70;
      root = insert_treenode(root, 50); //creating binary search tree
      insert_treenode(root, 30);
      insert_treenode(root, 20);
      insert_treenode(root, 40);
      insert_treenode(root, 70);
      insert_treenode(root, 60);
      insert_treenode(root, 80);
      
      cout << "Inorder traversal before reversing: " << endl;
      inorder_tree(root); //inorder of original tree
      cout << endl;
      Reverse_tree( & root, target, q1);
      cout << "Inorder traversal after reversing: " << endl;
      inorder_tree(root); //inorder of reversed tree
      return 0;
}

 

Output:

Inorder traversal before reversing: 
20 30 40 50 60 70 80 
Inorder traversal after reversing: 
20 30 40 70 60 50 80 

Implementation in Java 

import java.util.*;
public class reverse_Tree
{
   static class node
   {
       int key;
       node left, right;
   };
   static node root = null;
   static Queue < Integer > q1;
   static int target;
   static node newNode(int item)
   {
       node temp = new node();
       temp.key = item;
       temp.left = temp.right = null;
       return temp;
   }
   // for inorder traversal of BST
   static void inorder_tree(node root)
   {
       if (root != null)
       {
           inorder_tree(root.left);
           System.out.print(root.key + " ");
           inorder_tree(root.right);
       }
   }
   // reverse tree path using queue
   static void reversePath_queue(node node)
   {
       if (node == null) //If the tree is empty,
           return;
       if ((node).key == target) // If the node key equal to target
       {
           q1.add((node).key);
           (node).key = q1.peek();
           q1.remove();
           return;
       }
       // if key smaller than node key then
       else if (target < (node).key)
       {
           q1.add((node).key);
           // recursive call itself
           reversePath_queue((node).left);
           (node).key = q1.peek();
           q1.remove();
       }
       // if key greater than node key then
       else if (target > (node).key)
       {
           q1.add((node).key);
           // recursive call itself
           reversePath_queue((node).right);
           (node).key = q1.peek();
           q1.remove();
       }
       return;
   }
   static node insert_Node(node node, int key)
   {
       //If the tree is empty
       if (node == null)
           return newNode(key);
       if (key < node.key)
           node.left = insert_Node(node.left, key);
       else if (key > node.key)
           node.right = insert_Node(node.right, key);
       return node;
   }
   public static void main(String[] args)
   {
       q1 = new LinkedList < > ();
       target = 70;
       root = insert_Node(root, 50);
       root = insert_Node(root, 30);
       root = insert_Node(root, 20);
       root = insert_Node(root, 40);
       root = insert_Node(root, 70);
       root = insert_Node(root, 60);
       root = insert_Node(root, 80);
       
       System.out.print("Inorder traversal before reversing: "+ "\n");
       inorder_tree(root); //inorder traversal of the BST
       System.out.print("\n");
       // reverse path till target
       reversePath_queue(root);
       System.out.print("Inorder traversal after reversing: "
           +
           "\n");
       inorder_tree(root); //inorder traversal of the reversed BST
   }
}

 

Output:

Inorder traversal before reversing: 
20 30 40 50 60 70 80 
Inorder traversal after reversing: 
20 30 40 70 60 50 80 

 

Let us analyze the time and complexity of this approach.

Complexity analysis

Time complexity

This approach will take O(log n) where n is the size of the array. Because in this approach, we are making comparisons and are using recursive calls to solve the problem again and again. 

Space complexity

And it will take O(log n). Since we are not using any extra space to store it. 

Must Read  C Program to Reverse a Number

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What exactly is a leaf node?

A leaf node is any node in a binary tree or a tree that doesn't have any children. They are also called external nodes 

What is a binary search tree?

A binary search tree (BST) is a type of binary tree in which every internal node has a key. The rule for a binary search tree is:

a) A node's key can be greater than all of the keys in the node's left subtree.

b) A node can have a key that is less than the keys in the node's right subtree.

What do you know about an AVL tree?

An AVL tree is a self-balancing binary tree that compares the heights of its left and right subtrees and ensures the difference is less than one. This distinction is known as the balance factor.

BalanceFactor = height (Left subtree) – height (Right subtree)

Balance factor can have values -1, 0, 1.

Conclusion

To conclude this blog, firstly we discussed the problem statement on how to reverse a path in a binary search tree using a queue and different examples to understand the problem statement. For the recursive approach, we discussed its algorithm, implementations, and complexities. 

Check out this problem - Root To Leaf Path

For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Number of BSTs
Next article
Node with minimum value in a BST
Live masterclass