Increasing Order Search Tree - Leetcode Solution

Problem:

Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example:

Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Explanation:

    5
   / \
 3    6
/ \    \

2 4 8 / /
1 7 9

Output:

     1
      \
       2
        \
         3
          \
           4
            \
             5
              \
               6
                \
                 7
                  \
                   8
                    \
                     9

Solution:

There are multiple ways to solve this problem, but the most efficient way is to perform in-order traversal of the binary search tree and create a new tree with each node having no left child and only 1 right child.

Algorithm:

1. Create a new binary search tree
2. Perform in-order traversal of the given binary search tree
3. For each node during in-order traversal, do the following: a. Create a new node with the same value as the current node b. Add the new node to the new binary search tree c. If the new binary search tree already has a root, make the new node the right child of the previous node d. Make the new node the root of the new binary search tree if it has no root yet
4. Return the new binary search tree

Code:

/**

• Definition for a binary tree node.

• struct TreeNode {

• int val;
  

• TreeNode *left;
  

• TreeNode *right;
  

• TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  

• }; / class Solution { public: TreeNode increasingBST(TreeNode* root) { TreeNode* newRoot = NULL; TreeNode* currentNode = NULL;

   inOrderTraversal(root, newRoot, currentNode);
   
   return newRoot;
  

  }

  void inOrderTraversal(TreeNode* node, TreeNode*& newRoot, TreeNode*& currentNode) { if (node == NULL) { return; }

   inOrderTraversal(node->left, newRoot, currentNode);
   
   TreeNode* newNode = new TreeNode(node->val);
   if (newRoot == NULL) {
       newRoot = newNode;
   } else {
       currentNode->right = newNode;
   }
   currentNode = newNode;
   
   inOrderTraversal(node->right, newRoot, currentNode);
  

  } };

1