New answers tagged binary-search-trees
0
A simple way is as follows: do a symmetric visit of the BST (in time $O(n)$) and write down the elements in increasing order to an array $A$. Then reconstruct the BST from $A$.
If you're fine with a recursive algorithm, and the positions of $A$ are indexed form $0$ to $n-1$, then the root $r$ of the new BST will be exactly the element $A[\frac{n-1}{2}]$. ...
3
Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most $\epsilon n$ nodes. For the third vertex, it's at most $\epsilon^2 n$ nodes. For the $t$'th vertex, it's at most $\epsilon^{t-1} n$ nodes. If the path has ...
0
There are two common ways that the implementation of any B-tree variant decides if you're at a leaf node or not.
Most B-tree implementations include a tiny header in each node (e.g. to store the number of elements/pointers in the node). It might only be a word in size, but even then, it's usually not hard to find one spare bit to mark leaf nodes vs internal ...
0
Adding to the answer by HEKTO above, to calculate the rank in a BST with unique elements,
the rank of a left child = rank of the parent - 1 - number of elements in its right subtree
and,
the rank for a left child = rank of the parent + 1 + number of elements in its left subtree.
It can be used to find any general $i^{th}$ order statistic in the BST in O(...
0
The correct ordering is $8, 11, 10, 9, 13,16,18,15,13$
0
There are two 13 in the Binary Search Tree.
The left node of 15 can not be a 13 since it violates the BST property.
Instead, it can be replaced with 14 or any value in (13,15).
Resultant Traversal will be 8 11 10 9 x 16 18 15 13
where x is the value you choose to replace the left child of 15
0
Yes, it's wrong... The node 29 must be a left child of the node 35, the node 5 must be a left child of the node 15, and the node 69 must be a left child of the node 71 etc. - so, your algorithm makes wrong decision when there is a need to create a left child.
1
The property that makes a binary tree a binary search tree is that for every branch labeled $x$, all of the labels in the left subtree are smaller than $x$ and all of the labels in the right subtree are greater than $x$.
If you look at your tree, that property is violated in many places. For example, $5$ is in the right subtree of the node labeled $15$, yet ...
0
Remember that an in-order traversal lists the elements from left-to-right, descending the tree: Left, Root, and Right. This means that starting from the root (a), we will traverse the whole left branch, then print a, and finally traverse the right branch.
You started off correct; however, your mistake was that you put m beforee h. It is an easy mistake to ...
0
I know this is old but in response of @Trey here's the analysis.
We know that in BST you either go to left Subtree$(target > root)$ or Right Subtree $(target < root)$. In this process you can say that you will only search values between two ranges that depends on which path you want to proceed.
Here is a short Algorithm to describe it:
Let ...
1
I don't think that it is possible to balance a tree in logarithmic time:
An algorithm has to determine somehow, when it is finished
In this case, establishing that the tree is balanced is necessary
This operation alone is $\mathcal O(n)$ (count the height of left/right subtree)
Therefore, $\mathcal O(n)$ will be a lower bound for your algorithm and there ...
1
Do an inorder traversal of the BST...and store it in an array
the array will be sorted.
next construct a balanced binary search tree from this array.
1) Get the Middle of the array and make it root.
2) Recursively do same for left half and right half.
a) Get the middle of left half and make it left child of the root
created in step 1.
b) ...
Top 50 recent answers are included
