ProgramGuru

Convert a Binary Tree into a Binary Search Tree

Problem and examples

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.

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.

How it works

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.

  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).

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
};

void storeInorder(TreeNode* root, vector<int>& arr) {
    if (!root) return;
    storeInorder(root->left, arr);
    arr.push_back(root->val);
    storeInorder(root->right, arr);
}

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

TreeNode* binaryTreeToBST(TreeNode* root) {
    vector<int> arr;
    storeInorder(root, arr);
    sort(arr.begin(), arr.end());
    int idx = 0;
    arrayToBST(root, arr, idx);
    return root;
}

void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->val << " ";
    printInorder(root->right);
}

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

Python implementation

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

if __name__ == '__main__':
    root = TreeNode(10, TreeNode(30, TreeNode(20)), TreeNode(15, None, TreeNode(5)))
    binaryTreeToBST(root)
    result = []
    inorderTraversal(root, result)
    print(result)

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class BinaryTreeToBST {
    public void storeInorder(TreeNode root, List<Integer> arr) {
        if (root == null) return;
        storeInorder(root.left, arr);
        arr.add(root.val);
        storeInorder(root.right, arr);
    }

    public void arrayToBST(TreeNode root, Iterator<Integer> it) {
        if (root == null) return;
        arrayToBST(root.left, it);
        root.val = it.next();
        arrayToBST(root.right, it);
    }

    public TreeNode binaryTreeToBST(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        storeInorder(root, arr);
        Collections.sort(arr);
        arrayToBST(root, arr.iterator());
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(30);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(20);
        root.right.right = new TreeNode(5);
        BinaryTreeToBST converter = new BinaryTreeToBST();
        converter.binaryTreeToBST(root);
        List<Integer> result = new ArrayList<>();
        converter.storeInorder(root, result);
        System.out.println(result);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function storeInorder(root, arr) {
    if (!root) return;
    storeInorder(root.left, arr);
    arr.push(root.val);
    storeInorder(root.right, arr);
}

function arrayToBST(root, iterator) {
    if (!root) return;
    arrayToBST(root.left, iterator);
    root.val = iterator.next().value;
    arrayToBST(root.right, iterator);
}

function binaryTreeToBST(root) {
    const arr = [];
    storeInorder(root, arr);
    arr.sort((a, b) => a - b);
    const iterator = arr[Symbol.iterator]();
    arrayToBST(root, iterator);
    return root;
}

const root = new TreeNode(10, new TreeNode(30, new TreeNode(20)), new TreeNode(15, null, new TreeNode(5)));
binaryTreeToBST(root);

function printInorder(root) {
    if (!root) return [];
    return [...printInorder(root.left), root.val, ...printInorder(root.right)];
}

console.log(printInorder(root));

Go implementation

package main

import (
    "fmt"
    "sort"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func storeInorder(root *TreeNode, arr *[]int) {
    if root == nil {
        return
    }
    storeInorder(root.left, arr)
    *arr = append(*arr, root.val)
    storeInorder(root.right, arr)
}

func arrayToBST(root *TreeNode, arr *[]int, index *int) {
    if root == nil {
        return
    }
    arrayToBST(root.left, arr, index)
    root.val = (*arr)[*index]
    *index++
    arrayToBST(root.right, arr, index)
}

func binaryTreeToBST(root *TreeNode) *TreeNode {
    arr := []int{}
    storeInorder(root, &arr)
    sort.Ints(arr)
    idx := 0
    arrayToBST(root, &arr, &idx)
    return root
}

func printInorder(root *TreeNode) {
    if root == nil {
        return
    }
    printInorder(root.left)
    fmt.Print(root.val, " ")
    printInorder(root.right)
}

func main() {
    root := &TreeNode{10, &TreeNode{30, &TreeNode{20, nil, nil}, nil}, &TreeNode{15, nil, &TreeNode{5, nil, nil}}}
    binaryTreeToBST(root)
    printInorder(root)
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

type Tree = Option<Rc<RefCell<TreeNode>>>;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Tree,
    right: Tree,
}

fn store_inorder(node: &Tree, arr: &mut Vec<i32>) {
    if let Some(n) = node {
        let n = n.borrow();
        store_inorder(&n.left, arr);
        arr.push(n.val);
        store_inorder(&n.right, arr);
    }
}

fn array_to_bst(node: &Tree, arr: &mut Vec<i32>, idx: &mut usize) {
    if let Some(n) = node {
        let mut n = n.borrow_mut();
        array_to_bst(&n.left, arr, idx);
        n.val = arr[*idx];
        *idx += 1;
        array_to_bst(&n.right, arr, idx);
    }
}

fn binary_tree_to_bst(root: &Tree) {
    let mut arr = vec![];
    store_inorder(root, &mut arr);
    arr.sort();
    let mut idx = 0;
    array_to_bst(root, &mut arr, &mut idx);
}

fn print_inorder(node: &Tree) {
    if let Some(n) = node {
        let n = n.borrow();
        print_inorder(&n.left);
        print!("{} ", n.val);
        print_inorder(&n.right);
    }
}

fn main() {
    let root = Some(Rc::new(RefCell::new(TreeNode {
        val: 10,
        left: Some(Rc::new(RefCell::new(TreeNode {
            val: 30,
            left: Some(Rc::new(RefCell::new(TreeNode {
                val: 20,
                left: None,
                right: None,
            }))),
            right: None,
        }))),
        right: Some(Rc::new(RefCell::new(TreeNode {
            val: 15,
            left: None,
            right: Some(Rc::new(RefCell::new(TreeNode {
                val: 5,
                left: None,
                right: None,
            }))),
        }))),
    })));
    binary_tree_to_bst(&root);
    print_inorder(&root);
}

Kotlin implementation

data class TreeNode(var val: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun storeInorder(node: TreeNode?, arr: MutableList<Int>) {
    if (node == null) return
    storeInorder(node.left, arr)
    arr.add(node.val)
    storeInorder(node.right, arr)
}

fun arrayToBST(node: TreeNode?, arr: List<Int>, idx: IntArray) {
    if (node == null) return
    arrayToBST(node.left, arr, idx)
    node.val = arr[idx[0]++]
    arrayToBST(node.right, arr, idx)
}

fun binaryTreeToBST(root: TreeNode?): TreeNode? {
    val arr = mutableListOf<Int>()
    storeInorder(root, arr)
    arr.sort()
    val idx = intArrayOf(0)
    arrayToBST(root, arr, idx)
    return root
}

fun printInorder(root: TreeNode?) {
    if (root == null) return
    printInorder(root.left)
    print("${root.val} ")
    printInorder(root.right)
}

fun main() {
    val root = TreeNode(10,
        TreeNode(30, TreeNode(20)),
        TreeNode(15, null, TreeNode(5))
    )
    binaryTreeToBST(root)
    printInorder(root)
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
    }
}

func storeInorder(_ root: TreeNode?, _ arr: inout [Int]) {
    guard let root = root else { return }
    storeInorder(root.left, &arr)
    arr.append(root.val)
    storeInorder(root.right, &arr)
}

func arrayToBST(_ root: TreeNode?, _ arr: inout [Int], _ idx: inout Int) {
    guard let root = root else { return }
    arrayToBST(root.left, &arr, &idx)
    root.val = arr[idx]
    idx += 1
    arrayToBST(root.right, &arr, &idx)
}

func binaryTreeToBST(_ root: TreeNode?) -> TreeNode? {
    var arr = [Int]()
    storeInorder(root, &arr)
    arr.sort()
    var idx = 0
    arrayToBST(root, &arr, &idx)
    return root
}

func printInorder(_ root: TreeNode?) {
    guard let root = root else { return }
    printInorder(root.left)
    print(root.val, terminator: " ")
    printInorder(root.right)
}

let root = TreeNode(10)
root.left = TreeNode(30)
root.left?.left = TreeNode(20)
root.right = TreeNode(15)
root.right?.right = TreeNode(5)
binaryTreeToBST(root)
printInorder(root)

TypeScript implementation

class TreeNode {
    constructor(
        public val: number,
        public left: TreeNode | null = null,
        public right: TreeNode | null = null
    ) {}
}

function storeInorder(root: TreeNode | null, arr: number[]): void {
    if (!root) return;
    storeInorder(root.left, arr);
    arr.push(root.val);
    storeInorder(root.right, arr);
}

function arrayToBST(root: TreeNode | null, iterator: Iterator<number>): void {
    if (!root) return;
    arrayToBST(root.left, iterator);
    root.val = iterator.next().value!;
    arrayToBST(root.right, iterator);
}

function binaryTreeToBST(root: TreeNode | null): TreeNode | null {
    const arr: number[] = [];
    storeInorder(root, arr);
    arr.sort((a, b) => a - b);
    const iterator = arr[Symbol.iterator]();
    arrayToBST(root, iterator);
    return root;
}

function printInorder(root: TreeNode | null): number[] {
    if (!root) return [];
    return [...printInorder(root.left), root.val, ...printInorder(root.right)];
}

const root = new TreeNode(10, new TreeNode(30, new TreeNode(20)), new TreeNode(15, null, new TreeNode(5)));
binaryTreeToBST(root);
console.log(printInorder(root));