Convert a Binary Tree into a Binary Search Tree - Algorithm, Visualization, Examples

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given a Binary Tree (not necessarily a Binary Search Tree), convert it into a Binary Search Tree (BST) without changing the structure of the original tree. This means you should not add or remove any nodes; only the values of the nodes can be modified to make the tree satisfy the properties of a BST.

A Binary Search Tree is a binary tree in which for every node, the values in the left subtree are less than the node’s value, and the values in the right subtree are greater than the node’s value.

Examples❯

Input Binary Tree Converted BST Description
[10, 2, 7, 8, 4]
[4, 2, 8, null, null, 7, 10]
The in-order traversal of the input is [8, 2, 4, 10, 7] → sorted to [2, 4, 7, 8, 10], then reassigned to preserve original structure as BST.
[3, 1, 4, null, 2]
[3, 1, 4, null, 2]
This binary tree is already a BST. In-order: [1, 2, 3, 4] — sorted order matches structure.
[5, 3, 6, 2, 4, null, null, 1]
[4, 2, 5, 1, 3, null, null, null]
In-order of input: [1, 2, 3, 4, 5, 6] → sorted and reassigned to match the binary tree structure while making it a BST.
[1]
[1]
Single-node binary tree is already a valid BST.
[] [] Empty binary tree remains unchanged after conversion.

Solution❯

Case 1: Normal Binary Tree

In a typical binary tree, node values can be in any order, and they do not follow the BST property. The solution involves collecting all node values through an inorder traversal, which visits nodes in the left-root-right order. The collected values are then sorted, and another inorder traversal is performed to replace node values with the sorted ones. This ensures that the structure remains the same, but the values now satisfy BST properties.

Case 2: Tree Already a BST

If the tree is already a BST, the inorder traversal will return the values in sorted order. So even after performing the conversion algorithm, the values won't change. This is an idempotent operation—running it on a valid BST will not alter the tree.

Case 3: Single Node Tree

A single-node tree is always a BST by definition, as there are no subtrees to violate BST rules. Running the conversion algorithm has no effect, but it still works without errors. It's important for the algorithm to handle such trivial cases gracefully.

Case 4: Empty Tree

An empty binary tree has no nodes, so there are no values to process. The algorithm should detect this condition and skip all steps gracefully. The output in this case is simply another empty tree, and this ensures that our algorithm is robust and doesn't fail on empty input.

Case 5: Unbalanced Tree

In an unbalanced binary tree, nodes may be skewed to one side (like only right children). While the shape is unusual, the conversion still works. The algorithm doesn't rely on the balance of the tree; it only modifies the values while preserving the existing structure. After sorting and reassigning, the values are in proper BST order, even if the shape remains unbalanced.

Overall, this approach ensures that the tree structure remains intact, while the node values are adjusted to satisfy BST properties. It's particularly useful when we want to convert an arbitrary binary tree to a BST without restructuring it.

Algorithm Steps❯

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

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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)