# Level-traverse a binary tree

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7},

    3
/ \
9  20
/  \
15   7


return its level order traversal as:

[
,
[9,20],
[15,7]
]


The problem is pretty common level order traverse a binary tree but break each level into single array.

I implemented mine: I've designed a few test cases, but when I submit it to the OJ, it just complains about a runtime error. I don't quite understand where the problem is.

Full Sample

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > result;
if( root ) {
DFSVisit(root,0);
result.resize(n);
for( size_t i=0; i<n; i++ ){
while( (h ) ){
result[i].push_back( h->val );
h = h->left;
}
reverse( result[i].begin(), result[i].end() );
}
}
return result;

}

void DFSVisit( TreeNode* n, size_t level ){
//cerr << "DFSVISIT" << endl;
TreeNode* l = n->left;
TreeNode* r = n->right;
if( l  ) DFSVisit( l, level+1);
if( r  ) DFSVisit( r, level+1);
}

void AppendNodeToHeadlist( TreeNode* n, size_t l ){
//cerr << "DFSVISIT" << endl;
//printf( "healist size %lu \n", headlist.size() );
//printf( "node to append %d \n", n->val );
n->left = NULL;
}
else{

h->right = n;
n->left  = h;
//printf( "chain[%lu]: %d->%d\n",l, h->val, n->val );

}
}
};

void print_result( vector<vector<int> >& r ){
//cerr << "DFSVISIT" << endl;
for( size_t i=0; i<r.size(); i++ ){
for( size_t j=0; j<r[i].size(); j++ ){
printf( "%d ", r[i][j] );
}
printf( "\n" );
}
printf( "\n" );
}

void test_solution0(){

Solution s;
auto r = s.levelOrder(NULL);
vector<vector<int> > e;
if ( r == e ){
printf( "CASE0 PASSED!\n" );
}
else{
printf( "CASE0 FAILED!\n" );
printf( "===Actual   Result ===\n");
print_result( r );
printf( "===Expected Result ===\n");
print_result( e );
}

}

void test_solution1(){
TreeNode n1(1),n2(2),n3(3),n4(4),n5(5);
n1.left  = &n2;
n1.right = &n3;
n3.left  = &n4;
n3.right = &n5;

Solution s;
auto r = s.levelOrder(&n1);
vector<vector<int> > e = { {1}, {2,3}, {4,5} };
if ( r == e ){
printf( "CASE1 PASSED!\n" );
}
else{
printf( "CASE1 FAILED!\n" );
printf( "===Actual   Result ===\n");
print_result( r );
printf( "===Expected Result ===\n");
print_result( e );
}

}

void test_solution2(){
TreeNode n1(1),n2(2),n3(3),n4(4),n5(5), n6(6);
n1.left  = &n2;
n1.right = &n3;
n3.left  = &n4;
n3.right = &n5;
n2.left  = &n6;

Solution s;
auto r = s.levelOrder(&n1);
vector<vector<int> > e = { {1}, {2,3}, {6,4,5} };
if ( r == e ){
printf( "CASE2 PASSED!\n" );
}
else{
printf( "CASE2 FAILED!\n" );
printf( "===Actual   Result ===\n");
print_result( r );
printf( "===Expected Result ===\n");
print_result( e );
}

}

int main(){
test_solution0();
test_solution1();
test_solution2();
return 0;
}

• first of all it is not broken, it just didn't deal with boundary condition correctly. secondly this code is already written, you can run through the full sample link. – zinking May 27 '14 at 6:04