we know this definition:

Given a binary tree, Width of a tree is maximum of widths of all levels.

Let us consider the below example tree.

    /  \
   2    3
 /  \     \
4    5     8 
          /  \
         6    7

For the above tree, width of level 1 is 1, width of level 2 is 2, width of level 3 is 3 width of level 4 is 2.

So the maximum width of the tree is 3.

can we have a binary tree with Height $\Theta(n)$ and Width $\Theta(n)$

My solution: is YES. for example a binary tree with one-node:


am i right?

  • 1
    $\begingroup$ I am glad you got an answer which you accepted. But I still have a question: What is n? - - - Another point is that your example of a tree with only the root has height 0, not 1. $\endgroup$ – babou Aug 11 '14 at 15:40

Statements about $\Theta$-classes are statements about the behaviour of an algorithm/data structure, as (in this case) $n$ gets large. Thus, a single example can never prove such a statement. You'd have to provide a set that contains examples that become arbitrarily large and behave as desired. (The set, however, doesn't have to contain an example for every value of $n$.)

So you should try to construct such a set of examples. (And if you fail constantly, try to find out why. This might lead to a proof that no such set exists, i.e. the claim is false.)

  • $\begingroup$ Dear FranKw, you means we couldn't make a binary tree with Θ(n) in width and height. we must try a set of example for Θ. thanks. $\endgroup$ – Michle Moore Aug 11 '14 at 9:38

First, FrankW is right about you having to provide what he calls a set of examples (way of constructing a tree with those properties for most $n$ / a generic recipe)

However, while this set doesn't have to contain an example for every value on $n$, it should contain an example for every value above a certain $n_0$, which would also be a part of your solution (check the definition of $\Theta$, google "Big Oh"). In other words, for each $n$ above a certain $n_0$ (that you need to figure out), you need to able able to construct a tree with your desired properties for that $n$.

I also think you would have to clarify what exactly you mean by Width being $\Theta(n)$. Does that mean the Width of every level is in class $\Theta(n)$, or that the final (bottom) level is? Does it matter?

As for constructing the tree, here's a couple of guides that are hopefully not mistaken and leave a bit work for you to do yourself

  1. What's the minimal tree of height $n$ that you can come up with? What is its width at the bottom level?
  2. Is there a way of increasing the width of the minimal tree of height $n$ by one while keeping its height?
  3. Can you apply 2. until you get to width $n$?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.