# 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:

[
[3],
[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++ ){
TreeNode* h = headlist[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;
AppendNodeToHeadlist( n, level );
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 );
if( headlist.size() < l+1 ){
n->left = NULL;
}
else{

TreeNode* h = headlist[l];
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. May 27, 2014 at 6:04