Convert a Binary Tree into a Binary Search Tree - Visualization

Binary Search Trees

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❯

Understanding the Problem

We are given a Binary Tree, where nodes can have values in any order. Unlike a Binary Search Tree (BST), a Binary Tree doesn't guarantee that all left descendants are less than the root and all right descendants are greater. Our goal is to convert this Binary Tree into a BST, but without changing its structure.

This means that we can only change the node values, not the arrangement of nodes. The final tree should look the same in shape but must satisfy the BST property with the new values.

Step-by-Step Solution with Example

Step 1: Perform Inorder Traversal to Collect Values

Inorder traversal visits nodes in the left-root-right order. For any binary tree, this traversal doesn't guarantee sorted output, but it will help us collect all node values in a list.

Step 2: Sort the Collected Values

Once we have all the values in a list, we sort the list in ascending order. This sorted list represents how values should appear in inorder traversal for a valid BST.

Step 3: Perform Inorder Traversal Again to Replace Node Values

This time, during the inorder traversal, instead of collecting values, we replace each node’s value with the next value from the sorted list. Since inorder traversal visits nodes in the correct BST order (left-root-right), replacing values in this sequence ensures the BST property is satisfied.

Step 4: Example

Let's say we have the following binary tree:


      10
     /     30    15
   /        20       5

Inorder traversal of this tree: [20, 30, 10, 15, 5]

Sort the list: [5, 10, 15, 20, 30]

Replace values during inorder traversal:


      20
     /     10    30
   /        5       15

The structure remains the same, but now the values follow the BST rules.

Edge Cases

Case 1: Tree Already a BST

If the tree is already a BST, its inorder traversal is already sorted. Sorting and replacing with the same values has no effect. The operation is idempotent.

Case 2: Single Node Tree

A tree with just one node is trivially a BST. The algorithm still works and leaves the node unchanged.

Case 3: Empty Tree

An empty tree has no nodes to convert. The algorithm should detect this and return immediately. This ensures robustness.

Case 4: Unbalanced Tree

In an unbalanced tree (e.g., all nodes skewed to one side), the traversal and value replacement still work because the logic depends only on traversal, not shape.

Finally

This method of converting a binary tree to a BST is elegant and beginner-friendly. It works by rearranging node values rather than node positions, making it less complex. It also handles all edge cases gracefully, making the solution robust and widely applicable in real-world scenarios.

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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

// Tree node structure
typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void storeInorder(TreeNode* root, int arr[], int* idx) {
    if (!root) return;
    storeInorder(root->left, arr, idx);
    arr[(*idx)++] = root->val;
    storeInorder(root->right, arr, idx);
}

void arrayToBST(TreeNode* root, int arr[], int* idx) {
    if (!root) return;
    arrayToBST(root->left, arr, idx);
    root->val = arr[(*idx)++];
    arrayToBST(root->right, arr, idx);
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

TreeNode* binaryTreeToBST(TreeNode* root) {
    int arr[100], count = 0;
    storeInorder(root, arr, &count);
    qsort(arr, count, sizeof(int), compare);
    int idx = 0;
    arrayToBST(root, arr, &idx);
    return root;
}

void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    printf("%d ", root->val);
    printInorder(root->right);
}

int main() {
    TreeNode* root = createNode(10);
    root->left = createNode(30);
    root->right = createNode(15);
    root->left->left = createNode(20);
    root->right->right = createNode(5);
    binaryTreeToBST(root);
    printInorder(root);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...