Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order. I believe that I understood the three terms pretty well, and have tried several exercises and examples, which I got right. But I have problems when formulating a relation between these ways of traversing a tree with other properties of the tree. Take this exercise as an example: I have tried to draw several binary trees and to imagine some kind of relation between the numbers and the size of the subtrees, but always been unable to. Thanks for any help in advance! -- This exercise is from Open Data Structures (in pseudocode) from Pat Morin

A priority search tree is a binary tree satisfying the following: - every node $u$ stores a point $p_u = (x_u,y_u)$ - every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate. - If $v$ is a descendant of $u, y_v\leq y_u$. - If $v$ is in the left subtree of $u$, then $x_v Source: the above definition is a variant of the one used in this question: Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time I was wondering how, if given a set of $n$ points in general position sorted by $x$-coordinate, one could construct a priority search tree in worst case linear time? I know how to create a priority search tree in $O(n\log n)$ worst case time. I thought of creating a BST of x-coordinates and then doing an in-place fix with rotations to ensure the heap property is maintained. For each node $u,$ we can then let $x_u'=x_u$, the x-coordinate of the point it stores. However, this algorithm doesn't seem to run in linear time (since while doing the in-place fix the number of rotations could be close to linear for many points).

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big Theta in general but am having trouble understanding why they are used in such a way here. A source is linked but it does not seem to make any reference to Big Theta, only Big O. For example, why is the space complexity for the tree $\Theta(n)$ in the average case but $\mathrm{O}(n)$ in the worst case? My thought process is that since you always have to store all $n$ nodes in the tree, the space complexity is both $\Omega(n)$ and $\mathrm{O}(n)$, hence it should be $\Theta(n)$ in all cases. I don't see how there can be a "worst case" in terms of space when you're always storing the same amount of data. Similarly, for searching, why is the time complexity $\Theta(\log n)$ for the average case but $\mathrm{O}(\log n)$ in the worst case? To me this seems to imply you need to check at least some multiple of $\log n$ nodes in the average case, but not in the worst case? If the worst case is not bounded below by some multiple of $\log n$ (so could be lower in some cases), is this not a better scenario than what is given for the average case? Should it not be the other way round? It's a similar situation for insertion. I'm not sure what I'm misunderstanding about the operation of AVL trees, average vs. worst cases, or perhaps asymptotic notation in general, that's causing this misunderstanding. Is it just always convention to state worst case in terms of Big O?

My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees. I am confused about the following sentences: Consider any subtree of a binary search tree. It must contain keys in a contiguous range $k_i, …, k_j$ for some $1 \leq i \leq j \leq n$. In addition, a subtree that contains keys $k_i, …, k_j$ must also have as its leaves the dummy keys $d_{i-1}, … d_j$. (where $(k_j)_{j \in {[1,\ …,\ n]}}$ is a sorted sequence containing the keys of the nodes in the BST). The chapter does not include proof of this statement, which does not seem obvious to me at all. Moreover, I do not understand why the tree (key: $d_0$, right child: (key: $k_1$, right child: $d_1$)) — where $d_0$ is the dummy node corresponding to values strictly less than $k_1$ and $d_1$ is the dummy node corresponding to values strictly greater than $k_1$ — is not a satisfactory counterexample. It satisfies the BST property ($d_0 < k_1 < d_1$) and $k_1$ is not an ancestor of $d_0$. * Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein

My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?

I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables. I googled a lot for BST Representation of Hash Table. Code in C++ but didn't find any link or example. Can someone help me with the implementation. I'm really confused how to represend Key-Value pairs on BST. And what if there are collisions etc. All, I found was comparison b/w BST and HasTables: - https://stackoverflow.com/questions/22996474/why-implement-a-hashtable-with-a-binary-search-tree - https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/

I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My question is how do I get the average height of a BST with n nodes?

For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?

Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log n). So, in a course on data structures, is the study of BST's of any value except as a historical note?

Suppose that we have numbers between $1$ and $1000$ in a binary search tree and want to search for the number $363$. Which of the following sequences could not be the sequences of nodes examined ``` a) 924,220,911,244,898,258,362,363$ b) 925,202,911,240,912,245,363 c) 2,399,387,219,266,382,381,278,363 d) 935,278,347,621,299,392,358,363 e) 925, 202, 911, 240, 912, 245, 363 ``` I know that $d$ and $e$ are not valid sequences, my professor told us so. I know it has something to do the range between jumping from node to node, which has something to do with the following property of BST's Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$. I just don't see it, been trying to simulate the path sequence with no clear breakthrough.