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 Traversal

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.

Example  

Input

Reverse a Path in BST using QueuePin

Target Node = 12
Output

Please click Like if you loved this article?

Reverse a Path in BST using QueuePin

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.
See also
K’th Largest Element in BST when modification to BST is not allowed

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.

See also
Construct Complete Binary Tree from its Linked List Representation

References

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh