I have an theoretical question about `Balanced BST`

.

I would like to build `Perfect Balanced Tree`

that has `2^k - 1`

nodes, from a regular `unbalanced BST`

. The easiest solution I can think of is to use a sorted `Array/Linked list`

and recursively divide the array to sub-arrays, and build `Perfect Balanced BST`

from it.

However, in a case of extremely large Tree sizes, I will need to create an `Array/List`

in the same size so this method will consume a large amount of memory.

Another option is to use `AVL`

rotation functions, inserting element by element and balancing the tree with rotations depending on the Tree Balance Factor - three height of the left and right sub trees.

My questions are, am I right about my assumptions? Is there any other way to create a perfect `BST`

from unbalanced `BST`

?

AVL and similar trees are not *perfectly* balanced so I'm not sure how they are useful in this context.

You can build a doubly-linked list out of tree nodes, using `left`

and `right`

pointers in lieu of `forward`

and `backward`

pointers. Sort that list, and build the tree recursively from the bottom up, consuming the list from left to right.

Building a tree of size 1 is trivial: just bite the leftmost node off the list.

Now if you can build a tree of size `N`

, you can also build a tree of size `2N+1`

: build a tree of size `N`

, then bite off a single node, then build another tree of size `N`

. The singe node will be the root of your larger tree, and the two smaller trees will be its left and right subtrees. Since the list is sorted, the tree is automatically a valid search tree.

This is easy to modify for sizes other than `2^k-1`

too.

Update: since you are starting from a search tree, you can build a sorted list directly from it in `O(N)`

time and `O(log N)`

space (perhaps even in `O(1)`

space with a little ingenuity), and build the tree bottom-up also in `O(N)`

time and `O(log N)`

(or `O(1)`

) space.

I did not yet find a very good situation for needing a perfectly balanced search tree. If your case really needs it, I would like to hear about it. Usually it is better and faster to have a almost balanced tree.

If you have a large search tree, throwing away all existing structure is usually no good idea. Using rotation functions is a good way of getting a more balanced tree while preserving most of the existing structure. But normally you use a suitable data structure to make sure you never have a completely unbalanced tree. So called self balancing trees.

There is for example an AVL tree, a red-black-tree or a splay-tree, which use slightly different variants of rotation to keep the tree balanced.

If you really have a totally unbalanced tree you might have a different problem. - In your case rotating it the AVL way is probably the best way to fix it.

If you are memory constrained, then you can use the split and join operations which can be done on an AVL tree in O(log n) time, and I believe constant space.

If you also were able to maintain the order statistics, then you can split on median, make the LHS and RHS perfect and then join.

The pseudo-code (for a recursive version) will be

```
void MakePerfect (AVLTree tree) {
Tree left, right;
Data median;
SplitOnMedian(tree, &left, &median, &right);
left = MakePerfect(left);
right = MakePerfect(right);
return Join(left, median, right);
}
```

This can be implemented in O(n) time and O(log n) space, I believe.

Similar Questions

Ok, so I am currently trying to create a binary search tree, with each node containing a reference to some object, as well as a reference to its left child and a reference to its right child (3 variab

I was reading more on the binary search tree and then I found out about another variant of Binary Search Tree which is Splay tree and I am trying to implement it but somehow I got stuck. So the algori

I am trying to write a program that takes in strings and places them in a binary search tree in alphabetical order once these are inserted into the tree, a user prompts for one word to be deleted, thu

I need help in 3 tasks. I'm really new in Haskell and functional programming. data Tree = Node Int Tree Tree | Nil Define with help of the function collapse collapse :: Tree -> [Int] collapse N

I am trying to run my Binary Search Tree, I am creating objects of type Employee in my main program which does not seem to give me problems, but when I choose to search for an item in my BST, the prog

I have bought a nice little book about computational geometry and while reading it here and there I often stumbled over the use of these special kind of binary search tree. These trees are balanced an

I have a book that explains the theory behind binary search tree in a very bad way i know that there is something about the order of both left and right child but i still cannot get the idea about one

I'm trying to write a function that recursively goes through an array, inserting values into a tree while keeping the tree balanced. It's assumed that the array is sorted and that we know its size. I

I was reading through Introduction to algorithms i came across this problem about In-order Traversal of binary search tree without using a stack or recursion. Hint says to assume that testing of point

I've been working on implementing a binary search tree in C for a homework assignment in my programming class. After writing this much of the code and compiling in Visual Studio 2010, I get numerous e

I am making Binary Search Tree and AVL Tree for an assignment. I am having problem when I try to add 1,000,000 elements to Binary Search Tree but I can add key-> value pairs to AVL Tree.(There is n

I am trying to implement a method to create a node to insert into a binary tree (not bst). struct node{ struct node *left; int data; struct node *right; }; typedef struct node *n; void createNewNode()

Well i build a basic Binary Search Tree using a class called Node for simplicity i will include the core method that is used to insert Nodes public function addNode($node) { if ($this->left == null

I read on here of an exercise in interviews known as validating a binary search tree. How exactly does this work? What would one be looking for in validating a binary search tree? I have written a bas

I am just wondering if someone might be able to clarify the definition of a balanced tree for me. I have that a tree is balanced of each sub-tree is balanced and the height of the two sub-trees diffe

I am trying to understand why when deleting a node in a BST tree and having to keep the children and adhering to the BST structure, you have to either take the node's right child (higher value, then n

I have a binary tree of node containing an integer and a char. I'm working on Huffman Coding and I want to get the binary presentation of the nodes. A '0' is appended to the string for every left bran

Is there a javascript library that provides common data structures, e.g. priority queue, dictionary, and successor queries (balanced trees)? I could roll my own, but I'd rather have a black-box, espec

I have a perfect binary tree, i.e. each node in the tree is either a leaf node, or has two children, and all leaf nodes are on the same level. Each node has an index in depth-first order. (E.g. in a t

For a given binary tree, find the largest subtree which is also binary search tree? Example: Input: 10 / \ 50 150 / \ / \ 25 75 200 20 / \ / \ / \ / \ 15 35 65 30 120 135 155 250 Output: 50 / \ 25

and I was trying to implement a binary searching tree: template <typename T> bool Tree<T>::search(TreeNode<T> *ptr, const T &key) { if (ptr == 0) { cout<<No such data: &l

It's been a while from those school years. Got a job as IT specialist at a hospital. Trying to move to do some actual programming now. I'm working on binary trees now, and I was wondering what would b

If each node in a binary search tree stores its weight (number of nodes in its subtree), what would be an efficient method to compute a rank of a given node (its index in the sorted list) as I search

I am implementing code to construct BST(binary search tree) from a given post-order traversal array following this algorithm. I do not get back the binary Search Tree back. I am getting something that

So I am working on some homework and I have to complete a size balanced binary tree heap implementation, and I'm having some trouble with my enqueue function. We were given some code to start with and

I have a homework which ask from me to create a struct of binary search tree where its node of the binary search tree is another binary search tree. The first BST has the Surnames of Students and the

Disclaimer: This is for an assignment. I am not asking for explicit code answers, only help understanding why my code isn't working. I am trying to implement a basic Binary Search Tree, but I am havin

I am unsure as to what I need to do to search for a string stored in a binary tree. I have the search method written but I don't quite understand what to pass it. I need to search for the string befor

I am having an issue adding to my binary search tree, my program seems to be adding to a temporary structure instead. I think that in order for it to work correctly I have to call malloc for the left

I know we can preprocess and turn any binary search tree into a perfect binary tree using DSW algorithm or red black balanced trees. How do these two methods differ time-complexity wise? Can you provi

As mentioned in the Title , I have a Binary search tree. I want to convert it to sorted doubly linklist using recursion. My code for each node in tree find max of left sub-tree and assign its right t

I'm trying to traverse on a binary tree to find someone's ID by using his/her ID number. When I debug this function it works well, but on the other hand, when I directly run, it terminates itself.. Ca

I am trying to connect the siblings of the binary search tree. You can find the logic in the Connect() method. My question is, is there any better way to do it? Am I overdoing by using two queues to i

I'm looking for a data structure where each element in it has two keys. With one of them the structure is a BST and looking at the other one, data structure is a heap. With a little search, I found a

Why the search and successor and predecessor returns -1? // BST.cpp : main project file. #include stdafx.h #include <cstdlib> #include <iostream> #define SIZE 10 using namespace std; st

I am supposed to write a method that takes in two integers as a min and max. Then it removes any integers from the tree that are less than the minimum and larger than the maximum. The code I have so f

I'm working on a problem which requires me to copy a binary search tree recursively and to return the tree. I am coding in the binary search tree class, so it will copy whatever binary search tree it

How do you compute the average height of a binary search tree when adding 1000 random ints? What is the average height?

I am having trouble outputting a binary search tree. I have to build the tree, and then place all the doubles from the tree in order into a vector, and then output that vector in order. The problem I

I've been stuck on a question for a while and was wondering if anyone can point me in the right direction: Suppose binary heaps are represented using a pointer-based tree representation instead of an

I wanted to make a dictionary using BST but I did not have any Idea how to store them in the tree struct node { char word[50]; char meaning[256]; struct node *left, *right; }; I started like that but

This question already has an answer here: How do you validate a binary search tree? 18 answers Today I had an interview where I was asked to write a program which takes a Binary Tree and return

According to what explained in wiki I think dfs on a binary tree is the same one with preorder traversal root--left--right.(am i right?) But just did a little search and got this code, and the author

Say I have a binary tree with the following definition for a node. struct node { int key1 ; int key2 ; } The binary search tree is created on the basis of key1. Now is it possible to rearrange the

I am creating a simple binary search tree.When I am calling the add method using head pointer,changes made in the method are not reflected to this head pointer.It still points null. struct node *add(s

I have a homework assignment to implement a binary search tree (create, delete, search). I used the example provided by the teacher but I can't make it work. Here's my code so far: void insert_node(in

Given a binary search tree, i need to convert it into a doubly linked list(by traversing in zig zag order) using only pointers to structures in C++ as follows, Given Tree: 1 | +-------+---------+ | |

Im writing a binary search tree and i want to include a parent pointer. The way I have it now is that the parent reference is a node. so for example my getParent() returns a node rather than a value.

I'm learning Data Structures & Algorithms now. My lecture notes have an implementation of a binary search tree which is implemented using a recursive method. That is an elegant way, but my questio

I'm trying to make a list of all items in a binary search tree. I understand the recursion but I don't know how to make it return each value and then append it into a list. I want to create a function