# Can we construct a binary tree with width and height Θ(n)?

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.

     1
/  \
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:

     1


am i right?

• 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. – babou Aug 11 '14 at 15:40

## 2 Answers

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.)

• 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. – 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$?