Level-traverse a binary tree

Question

Level traverse binary tree question:

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 {
 vector<TreeNode*> headlist;
public:
 vector<vector<int> > levelOrder(TreeNode *root) {
 vector<vector<int> > result;
 if( root ) {
 DFSVisit(root,0);
 size_t n=headlist.size();
 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 ){
 headlist.push_back(NULL);
 headlist[l] = n;
 n->left = NULL;
 }
 else{
 TreeNode* h = headlist[l];
 h->right = n;
 n->left = h;
 headlist[l]=n;
 //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;
}

• zinking: 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.

Answer 1

I don't see why "DFS" should appear in your code. The challenge is to perform a breadth-first traversal. The typical way to implement a breadth-first traversal is to use a queue.

• zinking: you are correct, but I don't see issue implementing this way as well.