leetcode/level_traversal.cpp at master · Mayank-Parasar/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//
// Created by Mayank Parasar on 2020-03-01.
//

/*
 * You are given a tree, and your job is to print it level-by-level with linebreaks.

    a
   / \
  b   c
 / \ / \
d  e f  g

The output should be
a
bc
defg
 */

#include <iostream>
#include <vector>


using namespace std;

struct node {
    char val;
    node* left;
    node* right;

    node(char v) : val(v), left(nullptr), right(nullptr)
    { }
};

struct node_info{
    node* nde;
    int level;
};

std::vector<node_info> traversal;
// print level order traversal of the tree
// keep track of the level as you are traversing the tree...
void level_order_traversal(node* node_) {
    int level = 0;
    traversal.push_back({node_, level});
    int ii = 0;
    while (ii != traversal.size()){
        node * left_child = nullptr;
        node * right_child = nullptr;
        int next_level = traversal[ii].level + 1;
        if(traversal[ii].nde->left != nullptr) {
            left_child = traversal[ii].nde->left;
        }

        if(traversal[ii].nde->right != nullptr) {
            right_child = traversal[ii].nde->right;
        }

        if(left_child != nullptr)
            traversal.push_back({left_child, next_level});
        if(right_child != nullptr)
            traversal.push_back({right_child, next_level});

        ii++;
    }
}

void print_traversal(const std::vector<node_info>& traversal) {
    int ii;
    for(ii=0; ii < traversal.size()-1; ii++) {
        cout << traversal[ii].nde->val;
        if(traversal[ii].level < traversal[ii+1].level)
            cout << endl;
    }
    cout << traversal[ii].nde->val;
}

int main() {

    node* node_a = new node('a');
    node* node_b = new node('b');
    node* node_c = new node('c');
    node* node_d = new node('d');
    node* node_e = new node('e');
    node* node_f = new node('f');
    node* node_g = new node('g');

    // connect them
    node_a->left = node_b;
    node_a->right = node_c;
    node_b->left = node_d;
    node_b->right = node_e;
    node_c->left = node_f;
    node_c->right = node_g;

    level_order_traversal(node_a);
    print_traversal(traversal);

    return 0;
}