Runtime of tree sort algorithm confusion

Can anyone explain to me why the average runtime complexity of the program here – – is nlogn and not n^2logn? Similarly, why is the worst case time complexity n^2 and n^3?

The explanations for both the average and worst case runtime seem to only consider inserting the elements from the array into the tree. The runtime of doing an inorder tree traversal is O(n), so shouldn’t the runtimes in the link be multiplied by n?

Is it because the elements are simply being printed out and not added to a new array?

What is a good method for modelling combinatorial tree (sport competition results)?

Probably newbie question here, please point me out to relevant theories/tutorials if needed :

  • let say I want to evaluate the probabilities of the final rankings for a sport competition
  • the competition involved 8 teams, but I can simplify the problem to 4 contestants (say A – B – C – D)
    • the competition is splitted into n journeys during which every team faces another team (and only one). So with 4 contestants, I have 2 matches per journey
    • at the end of a match, 5 different points attributions are possible (depending on the score)

After one journey, there are 30 different possible combinations in terms of team’s points. So the model looks like a tree with a journey at each level.

Even if I simplify the situation to 2 journeys left, I can’t think of a elegant way to implement this problem (in Python for example) rather than “manually” creating the tree with the 30 combinations at each level and counting the leaves ?

I’m not familiar with this kind of problem so I’m not sure about the path forward.

Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes

I’m having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary tree whose levels are all full except for the last one in which all the nodes are as far left as possible.

I thought of proving it using induction but I’m not really sure how to do so. Any ideas?

How to solve this problem on tree?

Here is the link to original-problem :-

I will explain the statement shortly :

Given a tree with $ N$ nodes and a number $ D$ , calculate triples (u,v,w) such that dist($ u,v$ ) = dist($ v,w$ ) = dist($ u,w$ ) = $ D$ .

Constraint: $ N,D<=10^5.$


Node depth in randomly built binary search tree

It can be proved that randomly built binary search trees of size $ n$ are of depth $ O(log(n))$ and it is clear that level $ k$ has at most $ 2^{k}$ nodes (root’s level is 0).

I have an algorithm that traverses every path in the tree (beginning at the root) but stops after traversing $ k$ nodes (the parameter $ k$ is a configurable parameter which is independent of the size of the tree $ n$ ).

For any tree $ T$ with $ depth(T) > k$ , the algorithm will miss some nodes of the tree. I would like to bound the probability of my algorithm missing a large number of nodes.

Formalizing it: let $ T$ be a randomly built binary search tree of $ n$ nodes. I would like to calculate the probability for a node to have depth larger than $ k$ , as a function of $ n$ and $ k$ .