Teaching Kids Programming – Inorder Traversal Algorithm to Convert Binary Search Tree to Increasing Order Search Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of 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 one right child.

Example 1:
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]

Example 2:
Input: root = [5,1,7]
Output: [1,null,5,null,7]

Constraints:
The number of nodes in the given tree will be in the range [1, 100].

Inorder Traversal Algorithm to Convert Binary Search Tree to Increasing Order Search Tree

When we perform a inorder traversal on a Binary Search Tree, we get a sorted list. A Binary Search Tree is a binary tree where the left nodes are strictly smaller than the root nodes, and the right nodes are strictly larger than the root nodes. And also, there is no duplicate nodes.

The inorder gives us a sorted list, then we can build the tree aka increasing order search tree where it does not have left kids which is just like a singly linked list.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def increasingBST(self, root):
        def dfs(root):
            if not root:
                return []
            return dfs(root.left) + [root.val] + dfs(root.right)
        ans = cur = TreeNode(None)
        for v in dfs(root):
            cur.right = TreeNode(v)
            cur = cur.right
        return ans.right        

class Solution:
    def increasingBST(self, root):
        def dfs(root):
            if not root:
                return []
            return dfs(root.left) + [root.val] + dfs(root.right)
        ans = cur = TreeNode(None)
        for v in dfs(root):
            cur.right = TreeNode(v)
            cur = cur.right
        return ans.right        

We can also implement as a iterator which yields as we need.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def increasingBST(self, root):
        def inorder(node):
            if not node:
                return
            yield from inorder(node.left)
            yield node.val
            yield from inorder(node.right)
        ans = cur = TreeNode(None)
        for v in inorder(root):
            cur.right = TreeNode(v)
            cur = cur.right
        return ans.right

class Solution:
    def increasingBST(self, root):
        def inorder(node):
            if not node:
                return
            yield from inorder(node.left)
            yield node.val
            yield from inorder(node.right)
        ans = cur = TreeNode(None)
        for v in inorder(root):
            cur.right = TreeNode(v)
            cur = cur.right
        return ans.right

Space/Time complexity is O(N) as we need to visit N nodes exactly once, and need space for Recursion or storing the inorder traversal list.

–EOF (The Ultimate Computing & Technology Blog) —