Convert a Binary Tree into a Binary Search Tree

Algorithm Steps

Perform an inorder traversal of the binary tree and store all node values in an array.
Sort the array of values.
Perform another inorder traversal of the tree, and for each visited node, replace its value with the next value from the sorted array.
The tree now represents a Binary Search Tree (BST).

Convert a Binary Tree into a Binary Search Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderTraversal(root, arr):
    if root:
        inorderTraversal(root.left, arr)
        arr.append(root.val)
        inorderTraversal(root.right, arr)


def arrayToBST(root, arr_iter):
    if root:
        arrayToBST(root.left, arr_iter)
        root.val = next(arr_iter)
        arrayToBST(root.right, arr_iter)


def binaryTreeToBST(root):
    arr = []
    inorderTraversal(root, arr)
    arr.sort()
    arr_iter = iter(arr)
    arrayToBST(root, arr_iter)
    return root

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #        10
    #       /  \
    #      30   15
    #     /      \
    #    20       5
    root = TreeNode(10, TreeNode(30, TreeNode(20)), TreeNode(15, None, TreeNode(5)))
    binaryTreeToBST(root)
    result = []
    inorderTraversal(root, result)
    print(result)