Increasing Order Search Tree

The task is to rearrange the tree in in-order so that the leftmost node in the tree becomes the root of the tree, and every node has no left child and only one right child.

To do this, we can perform an in-order traversal of the binary search tree (BST) and link the nodes as we visit them.

Approach

1. Initialize Pointers: Create a dummy node and a current pointer. Set the current pointer to the dummy node.
2. In-Order Traversal: Perform an in-order traversal of the tree (left-root-right).
   • Visit Left: Recursively traverse the left subtree.
   • Visit Root: Set the right child of the current node to the root. Move the current pointer to its right child. Set the left child of the root to null.
   • Visit Right: Recursively traverse the right subtree.
3. Return Result: The new root of the tree will be the right child of the dummy node.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        def inOrder(node):
            nonlocal curr
            if not node:
                return

            inOrder(node.left)
            node.left = None
            curr.right = node
            curr = curr.right
            inOrder(node.right)

        dummy = TreeNode()
        curr = dummy
        inOrder(root)
        return dummy.right

Example

• Input: root = [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: By in-order traversal, we link nodes as we visit them, resulting in the desired structure.

Insights

• Time Complexity: The time complexity is (O(n)), where (n) is the number of nodes in the tree, as we visit each node exactly once.

• Space Complexity: The space complexity is (O(h)), where (h) is the height of the tree, since the in-order traversal uses recursive calls and consumes space on the call stack.

• In-Place Modification: This solution modifies the original tree in place without creating new nodes, achieving a space-efficient solution.

  1. Identify the traversal. Inorder traversal
  2. Keep all the values of the node in a list
  3. Traverse through the list and create the new tree
     • Keep previous node -
     • We need to traverse to the right
     • What should be the left child? None
     • What should be the right child?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {TreeNode}

def bst_wrapper(root, list)
      if root.nil?
        return 
    end
   
   bst_wrapper(root.left, list)
    list << root.val
    bst_wrapper(root.right, list)
end

def increasing_bst(root)
  list = []
    bst_wrapper(root, list)
    dummy = TreeNode.new
    current = dummy
    list.each do |n|
        node = TreeNode.new(n)
        current.right = node
        current = current.right
    end
    dummy.right
end