New answers tagged


According to this Wikipedia page: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes at the last level $h$. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some ...


I'd write a function which for each tree calculates the lowest common ancestor of all deepest nodes, and the height of the tree. This is quite simple: If the root R has no left or right branch, then the height is 1 and the common ancestor is R. If the root R has either a left or right branch, then calculate height and lowest common ancestor of that branch, ...


As @Rick Decker explained, you could have $n/2$ leaves at the max depth in the one case. In this case, step 3 is $O(n\log n)$. This post shows the worst case. Consider a tree $T$ consists of a chain of $n/2$ nodes where the remaining $n/2$ nodes are attached as a balanced tree at the bottom of the chain. This gives every leaf depth $n/2+\log_2(n)=\Theta(n)$ ...


Well, I don't know what you intend by "far less than" but it's clear that you could have about $n/2$ leaves at maximum depth: take a complete binary tree, for example, with the lowest level full.



Top 50 recent answers are included