# Reverse a Path in BST using Queue

Difficulty Level Medium
Frequently asked in Bloomberg Google Grofers HSBC Microsoft Target Corporation
Binary Search Tree Binary Tree Queue Traversal Tree Tree TraversalViews 948

In reverse a path in BST using queue problem we have given a Binary Search Tree and node, write an algorithm to reverse the path from root to the given node. Assume that the node exists in the BST.

Table of Contents

## Example

Input

Target Node = 12
Output

In-order traversal before the reversal
3 4 7 8 9 12 15 18
In-order traversal after reversal
3 4 7 12 15 8 9 18

## Algorithm for Reverse a Path in BST using Queue

Reversing a path from the root to the node is same as reversing the elements of the nodes on the path from the root to the node. For example, if the path from the root to the node is 5 -> 10 -> 15 -> 20, then reversing the path is the same as reversing the data. So the reversed path is 20 ->15 -> 10 -> 5.
The idea is to push all the values of nodes that come in the path from the root to the given node in a queue and after pushing replace the current node with the element at the front of the queue.

reversePathBST(root, target)

1. If the root is null, return.
2. If root’s value equals to the target, then push the root’s value to the queue and replace the root’s value with the element at the queue front. Remove the element at front of the queue.
3. Else if root’s value is less than the target, then push the root’s value to the queue, call reversePathBST recursively for root’s left child and then replace root’s value with the element at front of the queue. Also, remove the element at the front of the queue.
4. Else push the root’s value to the queue, call reversePathBST recursively for root’s right child and then replace root’s value by element present at the front of the queue. Also, remove the element at the front of the queue.

## JAVA Code for Reverse a Path in BST using Queue

```import java.util.LinkedList;
import java.util.Queue;

public class ReverseAPathInBSTUsingQueue {
// class representing node of a BST
static class Node {
int data;
Node left, right;

public Node(int data) {
this.data = data;
}
}

// queue used to reverse the path in BST
private static Queue<Integer> queue;

// function to print inorder traversal of a tree
private static void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}

private static void reversePath(Node root, int target) {
// if root is null return
if (root == null) {
return;
}

// add root's data to queue
queue.add(root.data);

if (root.data == target) {
// Base case
} else if (root.data > target) {
// target is in left sub tree
reversePath(root.left, target);
} else {
// target is in right sub tree
reversePath(root.right, target);
}

// replace root's data with front of queue
root.data = queue.poll();
}

public static void main(String[] args) {
// Example Tree
Node root = new Node(8);
root.left = new Node(4);
root.right = new Node(9);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.right = new Node(15);
root.right.right.left = new Node(12);
root.right.right.right = new Node(18);

// inorder traversal before reversing
System.out.println("Inorder before reversal");
inorder(root);
System.out.println();

queue = new LinkedList<>();
reversePath(root, 12);

// inorder traversal after reversing
System.out.println("Inorder after reversal");
inorder(root);
System.out.println();
}
}```
```Inorder before reversal
3 4 7 8 9 12 15 18
Inorder after reversal
3 4 7 12 15 8 9 18```

## C++ Code for Reverse a Path in BST using Queue

```#include <bits/stdc++.h>
using namespace std;

// class representing node of a BST
class Node {
public:
int data;
Node *left;
Node *right;

Node(int d) {
data = d;
left = right = NULL;
}
};

// queue used to reverse the path in BST
queue<int> q;

void inorder(Node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}

void reversePath(Node *root, int target) {
// if root is null return
if (root == NULL) {
return;
}

// add root's data to queue
q.push(root->data);

if (root->data == target) {
// Base case
} else if (root->data > target) {
// target is in left sub tree
reversePath(root->left, target);
} else {
// target is in right sub tree
reversePath(root->right, target);
}

// replace root's data with front of queue
root->data = q.front();
q.pop();
}

int main() {
// Example Tree
Node *root = new Node(8);
root->left = new Node(4);
root->right = new Node(9);
root->left->left = new Node(3);
root->left->right = new Node(7);
root->right->right = new Node(15);
root->right->right->left = new Node(12);
root->right->right->right = new Node(18);

// inorder traversal before reversing
cout<<"Inorder before reversal"<<endl;
inorder(root);
cout<<endl;

reversePath(root, 12);

// inorder traversal after reversing
cout<<"Inorder after reversal"<<endl;
inorder(root);
cout<<endl;

return 0;
}```
```Inorder before reversal
3 4 7 8 9 12 15 18
Inorder after reversal
3 4 7 12 15 8 9 18```

## Complexity Analysis

Time Complexity = O(log n)
Space Complexity = O(log n)
where n is the number of nodes in the Binary Search Tree.

References

Translate »