Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level.

Breadth First Search (BFS) is not allowed.3 / \ 9 20 / \ 15 7For example, the level order output of the tree above is:

`3 9 20 15 7`

In my last post: Printing Binary Tree in Level Order, we discuss how to print a tree using Breadth First Search (BFS). The challenge now is, can you do it using Depth First Search (DFS) this time?

**Hint:**

Write a function call *printLevel(BinaryTree *p, int level)* which will print all nodes of a given level. Assume you know the height of the tree, then you can print the entire tree level by level utilizing *printLevel*.

**Solution:***printLevel* function can be solved using DFS. Decrement level by *one* as you advance to the next level. When level equals *1*, you’ve reached the given level. To find the maximum height (or the max depth) of a tree, you can read my post: Maximum Height of a Binary Tree.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void printLevel(BinaryTree *p, int level) { if (!p) return; if (level == 1) { cout << p->data << " "; } else { printLevel(p->left, level-1); printLevel(p->right, level-1); } } void printLevelOrder(BinaryTree *root) { int height = maxHeight(root); for (int level = 1; level <= height; level++) { printLevel(root, level); cout << endl; } } |

**Further Thoughts:**

If you look carefully, you will notice that the DFS solution traverses the same node multiple times. Since BFS traverses each node exactly one time, BFS is much more efficient than DFS.

Could you find the run time complexity for the DFS level-order traversal solution? Try to estimate as best as you can, and then find the correct answer by proving it using Math. Does your estimate fares well with the correct answer? Why?

**Answer:**

Although the DFS solution traverse the same node multiple times, it is not another order slower than the BFS solution. Here is the proof that the DFS solution above runs in *O*(*N*) time, where *N* is the number of nodes in the binary tree and we assume that the binary tree is balanced.

We first compute the complexity of *printLevel* for the *kth* level:

T(k) = 2T(k-1) +c= 2^{k-1}T(1) +c= 2^{k-1}+c

Assuming it’s a balanced binary tree, then it would have a total of lg *N* levels.

Therefore, the complexity of printing all levels is:

T(1) + T(2) + ... + T(lgN) = 1 + 2 + 2^{2}+ ... + 2^{lg N-1}+ c =O(N)

Finding the maximum height of the tree also takes *O*(*N*) time, therefore the overall complexity is still *O*(*N*).

Nice solution man!!

-1@Elite(1337c0d3r)

I tried calculating the Big O and I think it should be NlogN, please follow this link

http://ideone.com/EjbXP

also when the tree is absolutely skewed, height shall be N, in that case it will be square(N)

N appears way too optimistic.

+7I think you don’t have to calculate the height. You can use the return value from printLevel, if you find at a specific level it’s all empty, return 0, and break the loop. Code could be like this:

int printLevel(BinaryTree *p, int level) {

__if (!p) return 0;

__if (level == 1) {

___cout <data <left, level-1);

___int rcright = printLevel(p->right, level-1);

___return rcleft || rcright;

}

}

+2… sorry I messed up the format, this one should be ok

int printLevel(BinaryTree *p, int level) {

__if (!p) return 0;

__if (level == 1) {

____cout <data <left, level-1);

____int rcright = printLevel(p->right, level-1);

____return rcleft || rcright;

__}

}

+1If the binary tree is not full then the code will not work.To avoid this first check that the left or right node of the tree is null.If it is null then don’t call printLevel function.

there is a slightly modification in the printLevel function

void printLevel(BinaryTree *p, int level) {

if (!p) return;

if (level == 1) {

cout <data <left!=NULL) //to check whether the left is NULL

printLevel(p->left, level-1);

if(p->right!=NULL) //to check whether the right is NULL

printLevel(p->right, level-1);

}

}

0sorry….there is some problem in the editor.It doen’t print as it was typed.

In the else part of printLevel function add two if statements to check whether the p->left and p->right is NULL.if it is not null then only call printLevel function

………

if(p->left!=NULL)

printLevel(p->left,level-1);

if(p->right!=NULL)

printLevel(p->right,level-1);

………..

-1Complexity should be nlogN

First iteration, nodes visited: 1

2nd : 1 + 2^1

3: 1+2^1+2^2

.

.

.

logn: 1+2^1+2^2 + …+2^(logn-1)

1+2^1+2^2 + …+2^(logn-1) = O(n)

Adding all : nLogn

0You may be wrong.

Adding all gives you: 2^(logN + 2) – logN – 2, which is O(N).

0To embed your code, please use

.

0Binary Tree Level-

Order Traversal Using

“Depth First Search

(DFS)”..?

How you say it’s DFS..?

0Hi,

the time complexity will be O(n*n)

+1Pingback: Binary Tree Traversal – Speculation437

Generally speaking, time complexity analysis should use worse-case. What is the worst case here? Skewed tree. What is the time complexity of level order traverse this skewed tree? O(n^2)

So the answer should be O(n^2)

+5@admin

What would be the worst case time complexity.Given a skewed tree its height would be the same as the number of nodes(N).So won’t it be O(2^N)???

0T(1) + T(2) + … + T(lg N)

= 1 + 2^1+ 2^2 + … + 2^(lg N-1) + c

=2^0 + 2^1+ 2^2 + … + 2^(lg N-1) + c

=1+2+4+…+N/2+c

=(1+N/2)*lgN/2+c

=O(NlgN)

How could it be O(N)?

0Even by intuition, since we are repeating the DFS process for printing each level( we always starts from the root and finished at the leaf, however we only print out the nodes in the exact level), we are repeating visiting N nodes for all lgN levels, so the expected complexity is O(NlgN). The worst case happens when it’s a skew tree, where O(N^2) complexity takes place.

+2Notice 3 5 6 7 are missing.

This is indeed O(N).

0in the sense of average runtime complexity of course.

0Consider this for the balanced case.

To traverse a balanced tree of height h (h = log n), we traverse 2^h – 1 nodes.

Then, for a tree of size n and height h (balanced):

2^0 + 2^1 + …. + 2^(h-1) + 2^h

This is a geometric series. Sum from 2^0 to 2^(m-1) for arbitrary reasonable m is 2^m – 1, thus, we have 2^h – 1 + 2^h = O(2^h) = O(n)

0Notice that each time ROOT is passed to printLevel, which is essentially a Preorder. This is O(nlogn). To make it O(n), return immediately when level<1.

0Also want to contribute my iterative solution:

-1Sorry didn’t notice this one requires DFS and my solution is the same as the one in your previous post.

0Worst case O(n^2) though.

0Just wanted to not that it’s not necessary to determine the tree height in advance. Please see my solution:

-1