Is there a way to build a balanced BST from sorted array so that the duplicates are only in right subtree?

Question

I need a function that takes as an argument pointer to sorted array and returns pointer to a balanced BST. My assumption is that for each node all nodes in left subtree are smaller and all nodes in right subtree are greater or equal than that node. My current attempt ensures a balanced BST but there are duplicates in both left and right subtree of a given node.

What follows is a minimal reproducible example:

#include <iostream>

struct node {
    int data;
    node* left;
    node* right;
    node(int d, node* l = nullptr, node* r = nullptr)
        : data(d), left(l), right(r) 
    {}
};

void release(node* root) {
    if (!root) return;
    release(root->left);
    release(root->right);
    delete root;
}

node* toTree(const int* sorted_data, int l, int r) {
    if (l > r) return nullptr;
    size_t m = (l + r) / 2;
    node* root = new node(sorted_data[m]);
    root->left = toTree(sorted_data, l, m - 1);
    root->right = toTree(sorted_data, m + 1, r);
    return root;
}

void printInorder(node* root) {
    if (!root) return;
    printInorder(root->left);
    std::cout << root->data << ' ';
    printInorder(root->right);
}

int main() {
    int arr[9] = { 1, 3, 3, 4, 4, 5, 6, 6, 7 };
    node* tree = toTree(arr, 0, 8);
    printInorder(tree);
    release(tree);
}

If I visualize the BST, it looks like:

         4 
   3          6
1    3      5   6
       4          7

According my assumption, the "4" at third level is not in correct subtree.

[OT] Consider std::unique_ptr instead of raw owning pointers. — Jarod42
– Jarod42, Commented Aug 29 at 9:05
@molbdnilo the problem I'm working on considers duplicates in BST. — yoan
– yoan, Commented Aug 30 at 10:57
Usually, a BST with duplicated keys stores either the multiplicity or all the equivalent elements in the key's node. — molbdnilo
– molbdnilo, Commented Aug 30 at 16:30

Jarod42 · Accepted Answer · 2025-08-29 09:03:46Z

8

Balanced is not possible, consider {2, 2, 2, 2, 2}, The only possible tree would be:

which is not balanced.

answered Aug 29 at 9:03

Jarod42

227k15 gold badges214 silver badges349 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Giles Ramoni Sep 26 at 1:48

Technically the predicate is usually less-than and not less-than-equal-to. so perhaps it could get a little bumpy, no?

Jarod42 Sep 26 at 7:16

OP stated than left children are "less-than" and right children are "greater-or-equal". if you don't have "equal" somewhere, duplicates would not be part of the regular tree. With single int as data, an extra counter might handle duplicates, for more complex cases, it might be not enough.

Collectives™ on Stack Overflow

Is there a way to build a balanced BST from sorted array so that the duplicates are only in right subtree?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related