Convert a Binary Search Tree into a Skewed tree in increasing or decreasing order

C++ Code

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

// Defining the structutre of TreeNode
struct TreeNode
{
   int data;
   TreeNode *left, *right;
   TreeNode(int x)
   {
       this->data = x;
       this->left = NULL;
       this->right = NULL;
   }
};

// Initializing global variables
TreeNode *headNode = NULL;
TreeNode *prevNode = NULL;

void BSTToSkewed(TreeNode *curr, int k)
{

   /*
   Base case, when the tree is empty
   we just return
   */
   if (curr == NULL)
   {
       return;
   }

   /*
   For k == 1, we need to construct
   the skewed tree in decresing order, so
   we traverse the right subtree first
   followed by the root and then the
   left subtree
   */
   if (k == 1)
   {
       BSTToSkewed(curr->right, k);
   }

   /*
   For k == 0, we need to construct
   the skewed tree in increasing order, so
   we traverse the left subtree first
   followed by the root and then the
   right subtree
   */
   else
   {
       BSTToSkewed(curr->left, k);
   }

   /*
   Storing the reference to
   the left and the right subtree
   so that we do not lose their
   refrence while adjusting the
   pointers
   */
   TreeNode *leftSubTree = curr->left;
   TreeNode *rightSubTree = curr->right;

   /*
   Adjusting the pointers
   to construct the desired tree (skewed)
   */
   if (headNode == NULL)
   {
       headNode = curr;
       prevNode = curr;
   }
   else
   {
       prevNode->right = curr;
       curr->left = NULL;
       prevNode = curr;
   }

   if (k == 1)
   {
       BSTToSkewed(leftSubTree, k);
   }
   else
   {
       BSTToSkewed(rightSubTree, k);
   }
}

// Entry point
int main()
{

   // Creating a binary search tree
   TreeNode *root = new TreeNode(10);
   root->left = new TreeNode(5);
   root->left->left = new TreeNode(1);
   root->left->right = new TreeNode(6);
   root->right = new TreeNode(12);
   root->right->left = new TreeNode(11);
   root->right->right = new TreeNode(15);

   /*
   Toggle between the lines 106 and 107
   by commenting/uncommenting to test both
   cases i.e. k = 0 or k = 1
   int k = 0;
   */
   int k = 1;

   /*
   Converting the binary search tree into a
   increasing / decreasing skewed tree
   */
   BSTToSkewed(root, k);

   // Traversing the skewed tree
   while (headNode != NULL)
   {
       cout << headNode->data << " ";
       headNode = headNode->right;
   }
   cout << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

When K = 0, 

1 5 6 10 11 12 15

​​When K = 1, 

15 12 11 10 6 5 1

Complexity Analysis

Time complexity: Since we are doing an inorder traversal of the tree, the time complexity is O(N), where ‘N’ is the number of nodes in the tree. 

Space complexity: We are not using any extra space to solve the given problem; hence the space complexity is O(1). 

Note: We are not considering the recursion call stack in our space complexity analysis. 

FAQs

1.Can this problem be solved in less than O(N) time? 

•  No! this is the most optimal solution to the problem. In order to solve this problem, we must visit every node in the tree; hence the time complexity is O(N) and can not be reduced any further. 

2.Which tree traversal technique is used for obtaining elements of a binary search tree in sorted order? 

• Inorder traversal.  

Key Takeaways

In this blog, we solved a really interesting problem: “Convert a Binary Search Tree into a Skewed tree in increasing or decreasing order”. We also discussed the time and space complexity of our solution. Remember, always try to find the time and space complexity of your solutions because you will be asked to find the complexities of your solutions in your interviews. If you love solving coding problems, please visit this incredible platform Coding Ninjas Studio.

Do check out our DSA course, to master data structures and algorithms and ace coding interviews.

Check out this problem - Diameter Of Binary Tree

If you feel that this blog has helped you in any way, then please do share it with your friends. 

Happy Coding!