/st-gathering

Data Gathering Spanning Tree Algorithm

Primary LanguageGo

Data Gathering Spanning Tree

Description

This project implements a data gathering spanning tree algorithm in Go. It also implements a version of the algorithm where the nodes immediately forward the data to their parent, when receiving it from their children.

The trees used in the tests are generated as balanced binary trees. The root node is always node 0.

How to run

go run main.go <num_nodes>

Results

Number of Messages

# Nodes Data Gathering ST Data Gathering ST forwarding data to parent
3 2 2
5 4 6
10 9 21
20 19 59
40 39 155
80 79 387
160 159 931
256 255 1,667
320 319 2,179
640 639 4,747
1,280 1,279 10,764
5,000 4,999 51,822
10,000 9,999 113,631
50,000 49,999 684,481
500,000 499,999 8,475,732
1,000,000 999,999 17,951,445

Time

# Nodes Data Gathering ST Data Gathering ST forwarding data to parent
3 119.375µs 143.125µs
5 131.583µs 237.083µs
10 270.417µs 394.75µs
20 326.916µs 870.958µs
40 694.916µs 1.610583ms
80 1.3635ms 4.060209ms
160 2.210042ms 14.107625ms
256 4.773833ms 23.863417ms
320 5.11475ms 32.046375ms
640 13.093708ms 56.361333ms
1,280 26.571166ms 92.647209ms
5,000 88.373708ms 486.880167ms
10,000 168.962625ms 1.0585515s
50,000 808.111917ms 6.115064542s
500,000 8.105962584s 1m13.704364917s
1,000,000 21.150660042s 2m47.6733755s

Trees used

3 nodes

└── Node ID: 0
    ├── Node ID: 1
    └── Node ID: 2

5 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   └── Node ID: 3
    └── Node ID: 2
        └── Node ID: 4

10 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   ├── Node ID: 6
    │   └── Node ID: 3
    │       └── Node ID: 5
    │           ├── Node ID: 8
    │           └── Node ID: 9
    └── Node ID: 2
        ├── Node ID: 7
        └── Node ID: 4

20 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   ├── Node ID: 6
    │   │   ├── Node ID: 10
    │   │   └── Node ID: 11
    │   └── Node ID: 3
    │       └── Node ID: 5
    │           ├── Node ID: 8
    │           │   ├── Node ID: 14
    │           │   └── Node ID: 15
    │           └── Node ID: 9
    │               ├── Node ID: 16
    │               └── Node ID: 17
    └── Node ID: 2
        ├── Node ID: 7
        │   ├── Node ID: 12
        │   └── Node ID: 13
        └── Node ID: 4
            ├── Node ID: 18
            └── Node ID: 19

40 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   ├── Node ID: 6
    │   │   ├── Node ID: 10
    │   │   │   ├── Node ID: 20
    │   │   │   └── Node ID: 21
    │   │   └── Node ID: 11
    │   │       ├── Node ID: 22
    │   │       └── Node ID: 23
    │   └── Node ID: 3
    │       └── Node ID: 5
    │           ├── Node ID: 8
    │           │   ├── Node ID: 14
    │           │   │   ├── Node ID: 28
    │           │   │   └── Node ID: 29
    │           │   └── Node ID: 15
    │           │       ├── Node ID: 30
    │           │       └── Node ID: 31
    │           └── Node ID: 9
    │               ├── Node ID: 16
    │               │   ├── Node ID: 32
    │               │   └── Node ID: 33
    │               └── Node ID: 17
    │                   ├── Node ID: 34
    │                   └── Node ID: 35
    └── Node ID: 2
        ├── Node ID: 7
        │   ├── Node ID: 12
        │   │   ├── Node ID: 24
        │   │   └── Node ID: 25
        │   └── Node ID: 13
        │       ├── Node ID: 26
        │       └── Node ID: 27
        └── Node ID: 4
            ├── Node ID: 18
            │   ├── Node ID: 36
            │   └── Node ID: 37
            └── Node ID: 19
                ├── Node ID: 38
                └── Node ID: 39

80 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   ├── Node ID: 6
    │   │   ├── Node ID: 10
    │   │   │   ├── Node ID: 20
    │   │   │   │   ├── Node ID: 40
    │   │   │   │   └── Node ID: 41
    │   │   │   └── Node ID: 21
    │   │   │       ├── Node ID: 42
    │   │   │       └── Node ID: 43
    │   │   └── Node ID: 11
    │   │       ├── Node ID: 22
    │   │       │   ├── Node ID: 44
    │   │       │   └── Node ID: 45
    │   │       └── Node ID: 23
    │   │           ├── Node ID: 46
    │   │           └── Node ID: 47
    │   └── Node ID: 3
    │       └── Node ID: 5
    │           ├── Node ID: 8
    │           │   ├── Node ID: 14
    │           │   │   ├── Node ID: 28
    │           │   │   │   ├── Node ID: 56
    │           │   │   │   └── Node ID: 57
    │           │   │   └── Node ID: 29
    │           │   │       ├── Node ID: 58
    │           │   │       └── Node ID: 59
    │           │   └── Node ID: 15
    │           │       ├── Node ID: 30
    │           │       │   ├── Node ID: 60
    │           │       │   └── Node ID: 61
    │           │       └── Node ID: 31
    │           │           ├── Node ID: 62
    │           │           └── Node ID: 63
    │           └── Node ID: 9
    │               ├── Node ID: 16
    │               │   ├── Node ID: 32
    │               │   │   ├── Node ID: 64
    │               │   │   └── Node ID: 65
    │               │   └── Node ID: 33
    │               │       ├── Node ID: 66
    │               │       └── Node ID: 67
    │               └── Node ID: 17
    │                   ├── Node ID: 34
    │                   │   ├── Node ID: 68
    │                   │   └── Node ID: 69
    │                   └── Node ID: 35
    │                       ├── Node ID: 70
    │                       └── Node ID: 71
    └── Node ID: 2
        ├── Node ID: 7
        │   ├── Node ID: 12
        │   │   ├── Node ID: 24
        │   │   │   ├── Node ID: 48
        │   │   │   └── Node ID: 49
        │   │   └── Node ID: 25
        │   │       ├── Node ID: 50
        │   │       └── Node ID: 51
        │   └── Node ID: 13
        │       ├── Node ID: 26
        │       │   ├── Node ID: 52
        │       │   └── Node ID: 53
        │       └── Node ID: 27
        │           ├── Node ID: 54
        │           └── Node ID: 55
        └── Node ID: 4
            ├── Node ID: 18
            │   ├── Node ID: 36
            │   │   ├── Node ID: 72
            │   │   └── Node ID: 73
            │   └── Node ID: 37
            │       ├── Node ID: 74
            │       └── Node ID: 75
            └── Node ID: 19
                ├── Node ID: 38
                │   ├── Node ID: 76
                │   └── Node ID: 77
                └── Node ID: 39
                    ├── Node ID: 78
                    └── Node ID: 79

160 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   ├── Node ID: 6
    │   │   ├── Node ID: 10
    │   │   │   ├── Node ID: 20
    │   │   │   │   ├── Node ID: 40
    │   │   │   │   │   ├── Node ID: 80
    │   │   │   │   │   └── Node ID: 81
    │   │   │   │   └── Node ID: 41
    │   │   │   │       ├── Node ID: 82
    │   │   │   │       └── Node ID: 83
    │   │   │   └── Node ID: 21
    │   │   │       ├── Node ID: 42
    │   │   │       │   ├── Node ID: 84
    │   │   │       │   └── Node ID: 85
    │   │   │       └── Node ID: 43
    │   │   │           ├── Node ID: 86
    │   │   │           └── Node ID: 87
    │   │   └── Node ID: 11
    │   │       ├── Node ID: 22
    │   │       │   ├── Node ID: 44
    │   │       │   │   ├── Node ID: 88
    │   │       │   │   └── Node ID: 89
    │   │       │   └── Node ID: 45
    │   │       │       ├── Node ID: 90
    │   │       │       └── Node ID: 91
    │   │       └── Node ID: 23
    │   │           ├── Node ID: 46
    │   │           │   ├── Node ID: 92
    │   │           │   └── Node ID: 93
    │   │           └── Node ID: 47
    │   │               ├── Node ID: 94
    │   │               └── Node ID: 95
    │   └── Node ID: 3
    │       └── Node ID: 5
    │           ├── Node ID: 8
    │           │   ├── Node ID: 14
    │           │   │   ├── Node ID: 28
    │           │   │   │   ├── Node ID: 56
    │           │   │   │   │   ├── Node ID: 112
    │           │   │   │   │   └── Node ID: 113
    │           │   │   │   └── Node ID: 57
    │           │   │   │       ├── Node ID: 114
    │           │   │   │       └── Node ID: 115
    │           │   │   └── Node ID: 29
    │           │   │       ├── Node ID: 58
    │           │   │       │   ├── Node ID: 116
    │           │   │       │   └── Node ID: 117
    │           │   │       └── Node ID: 59
    │           │   │           ├── Node ID: 118
    │           │   │           └── Node ID: 119
    │           │   └── Node ID: 15
    │           │       ├── Node ID: 30
    │           │       │   ├── Node ID: 60
    │           │       │   │   ├── Node ID: 120
    │           │       │   │   └── Node ID: 121
    │           │       │   └── Node ID: 61
    │           │       │       ├── Node ID: 122
    │           │       │       └── Node ID: 123
    │           │       └── Node ID: 31
    │           │           ├── Node ID: 62
    │           │           │   ├── Node ID: 124
    │           │           │   └── Node ID: 125
    │           │           └── Node ID: 63
    │           │               ├── Node ID: 126
    │           │               └── Node ID: 127
    │           └── Node ID: 9
    │               ├── Node ID: 16
    │               │   ├── Node ID: 32
    │               │   │   ├── Node ID: 64
    │               │   │   │   ├── Node ID: 128
    │               │   │   │   └── Node ID: 129
    │               │   │   └── Node ID: 65
    │               │   │       ├── Node ID: 130
    │               │   │       └── Node ID: 131
    │               │   └── Node ID: 33
    │               │       ├── Node ID: 66
    │               │       │   ├── Node ID: 132
    │               │       │   └── Node ID: 133
    │               │       └── Node ID: 67
    │               │           ├── Node ID: 134
    │               │           └── Node ID: 135
    │               └── Node ID: 17
    │                   ├── Node ID: 34
    │                   │   ├── Node ID: 68
    │                   │   │   ├── Node ID: 136
    │                   │   │   └── Node ID: 137
    │                   │   └── Node ID: 69
    │                   │       ├── Node ID: 138
    │                   │       └── Node ID: 139
    │                   └── Node ID: 35
    │                       ├── Node ID: 70
    │                       │   ├── Node ID: 140
    │                       │   └── Node ID: 141
    │                       └── Node ID: 71
    │                           ├── Node ID: 142
    │                           └── Node ID: 143
    └── Node ID: 2
        ├── Node ID: 7
        │   ├── Node ID: 12
        │   │   ├── Node ID: 24
        │   │   │   ├── Node ID: 48
        │   │   │   │   ├── Node ID: 96
        │   │   │   │   └── Node ID: 97
        │   │   │   └── Node ID: 49
        │   │   │       ├── Node ID: 98
        │   │   │       └── Node ID: 99
        │   │   └── Node ID: 25
        │   │       ├── Node ID: 50
        │   │       │   ├── Node ID: 100
        │   │       │   └── Node ID: 101
        │   │       └── Node ID: 51
        │   │           ├── Node ID: 102
        │   │           └── Node ID: 103
        │   └── Node ID: 13
        │       ├── Node ID: 26
        │       │   ├── Node ID: 52
        │       │   │   ├── Node ID: 104
        │       │   │   └── Node ID: 105
        │       │   └── Node ID: 53
        │       │       ├── Node ID: 106
        │       │       └── Node ID: 107
        │       └── Node ID: 27
        │           ├── Node ID: 54
        │           │   ├── Node ID: 108
        │           │   └── Node ID: 109
        │           └── Node ID: 55
        │               ├── Node ID: 110
        │               └── Node ID: 111
        └── Node ID: 4
            ├── Node ID: 18
            │   ├── Node ID: 36
            │   │   ├── Node ID: 72
            │   │   │   ├── Node ID: 144
            │   │   │   └── Node ID: 145
            │   │   └── Node ID: 73
            │   │       ├── Node ID: 146
            │   │       └── Node ID: 147
            │   └── Node ID: 37
            │       ├── Node ID: 74
            │       │   ├── Node ID: 148
            │       │   └── Node ID: 149
            │       └── Node ID: 75
            │           ├── Node ID: 150
            │           └── Node ID: 151
            └── Node ID: 19
                ├── Node ID: 38
                │   ├── Node ID: 76
                │   │   ├── Node ID: 152
                │   │   └── Node ID: 153
                │   └── Node ID: 77
                │       ├── Node ID: 154
                │       └── Node ID: 155
                └── Node ID: 39
                    ├── Node ID: 78
                    │   ├── Node ID: 156
                    │   └── Node ID: 157
                    └── Node ID: 79
                        ├── Node ID: 158
                        └── Node ID: 159

256 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   ├── Node ID: 6
    │   │   ├── Node ID: 10
    │   │   │   ├── Node ID: 20
    │   │   │   │   ├── Node ID: 40
    │   │   │   │   │   ├── Node ID: 80
    │   │   │   │   │   │   ├── Node ID: 160
    │   │   │   │   │   │   └── Node ID: 161
    │   │   │   │   │   └── Node ID: 81
    │   │   │   │   │       ├── Node ID: 162
    │   │   │   │   │       └── Node ID: 163
    │   │   │   │   └── Node ID: 41
    │   │   │   │       ├── Node ID: 82
    │   │   │   │       │   ├── Node ID: 164
    │   │   │   │       │   └── Node ID: 165
    │   │   │   │       └── Node ID: 83
    │   │   │   │           ├── Node ID: 166
    │   │   │   │           └── Node ID: 167
    │   │   │   └── Node ID: 21
    │   │   │       ├── Node ID: 42
    │   │   │       │   ├── Node ID: 84
    │   │   │       │   │   ├── Node ID: 168
    │   │   │       │   │   └── Node ID: 169
    │   │   │       │   └── Node ID: 85
    │   │   │       │       ├── Node ID: 170
    │   │   │       │       └── Node ID: 171
    │   │   │       └── Node ID: 43
    │   │   │           ├── Node ID: 86
    │   │   │           │   ├── Node ID: 172
    │   │   │           │   └── Node ID: 173
    │   │   │           └── Node ID: 87
    │   │   │               ├── Node ID: 174
    │   │   │               └── Node ID: 175
    │   │   └── Node ID: 11
    │   │       ├── Node ID: 22
    │   │       │   ├── Node ID: 44
    │   │       │   │   ├── Node ID: 88
    │   │       │   │   │   ├── Node ID: 176
    │   │       │   │   │   └── Node ID: 177
    │   │       │   │   └── Node ID: 89
    │   │       │   │       ├── Node ID: 178
    │   │       │   │       └── Node ID: 179
    │   │       │   └── Node ID: 45
    │   │       │       ├── Node ID: 90
    │   │       │       │   ├── Node ID: 180
    │   │       │       │   └── Node ID: 181
    │   │       │       └── Node ID: 91
    │   │       │           ├── Node ID: 182
    │   │       │           └── Node ID: 183
    │   │       └── Node ID: 23
    │   │           ├── Node ID: 46
    │   │           │   ├── Node ID: 92
    │   │           │   │   ├── Node ID: 184
    │   │           │   │   └── Node ID: 185
    │   │           │   └── Node ID: 93
    │   │           │       ├── Node ID: 186
    │   │           │       └── Node ID: 187
    │   │           └── Node ID: 47
    │   │               ├── Node ID: 94
    │   │               │   ├── Node ID: 188
    │   │               │   └── Node ID: 189
    │   │               └── Node ID: 95
    │   │                   ├── Node ID: 190
    │   │                   └── Node ID: 191
    │   └── Node ID: 3
    │       └── Node ID: 5
    │           ├── Node ID: 8
    │           │   ├── Node ID: 14
    │           │   │   ├── Node ID: 28
    │           │   │   │   ├── Node ID: 56
    │           │   │   │   │   ├── Node ID: 112
    │           │   │   │   │   │   ├── Node ID: 224
    │           │   │   │   │   │   └── Node ID: 225
    │           │   │   │   │   └── Node ID: 113
    │           │   │   │   │       ├── Node ID: 226
    │           │   │   │   │       └── Node ID: 227
    │           │   │   │   └── Node ID: 57
    │           │   │   │       ├── Node ID: 114
    │           │   │   │       │   ├── Node ID: 228
    │           │   │   │       │   └── Node ID: 229
    │           │   │   │       └── Node ID: 115
    │           │   │   │           ├── Node ID: 230
    │           │   │   │           └── Node ID: 231
    │           │   │   └── Node ID: 29
    │           │   │       ├── Node ID: 58
    │           │   │       │   ├── Node ID: 116
    │           │   │       │   │   ├── Node ID: 232
    │           │   │       │   │   └── Node ID: 233
    │           │   │       │   └── Node ID: 117
    │           │   │       │       ├── Node ID: 234
    │           │   │       │       └── Node ID: 235
    │           │   │       └── Node ID: 59
    │           │   │           ├── Node ID: 118
    │           │   │           │   ├── Node ID: 236
    │           │   │           │   └── Node ID: 237
    │           │   │           └── Node ID: 119
    │           │   │               ├── Node ID: 238
    │           │   │               └── Node ID: 239
    │           │   └── Node ID: 15
    │           │       ├── Node ID: 30
    │           │       │   ├── Node ID: 60
    │           │       │   │   ├── Node ID: 120
    │           │       │   │   │   ├── Node ID: 240
    │           │       │   │   │   └── Node ID: 241
    │           │       │   │   └── Node ID: 121
    │           │       │   │       ├── Node ID: 242
    │           │       │   │       └── Node ID: 243
    │           │       │   └── Node ID: 61
    │           │       │       ├── Node ID: 122
    │           │       │       │   ├── Node ID: 244
    │           │       │       │   └── Node ID: 245
    │           │       │       └── Node ID: 123
    │           │       │           ├── Node ID: 246
    │           │       │           └── Node ID: 247
    │           │       └── Node ID: 31
    │           │           ├── Node ID: 62
    │           │           │   ├── Node ID: 124
    │           │           │   │   ├── Node ID: 248
    │           │           │   │   └── Node ID: 249
    │           │           │   └── Node ID: 125
    │           │           │       ├── Node ID: 250
    │           │           │       └── Node ID: 251
    │           │           └── Node ID: 63
    │           │               ├── Node ID: 126
    │           │               │   ├── Node ID: 252
    │           │               │   └── Node ID: 253
    │           │               └── Node ID: 127
    │           │                   ├── Node ID: 254
    │           │                   └── Node ID: 255
    │           └── Node ID: 9
    │               ├── Node ID: 16
    │               │   ├── Node ID: 32
    │               │   │   ├── Node ID: 64
    │               │   │   │   ├── Node ID: 128
    │               │   │   │   └── Node ID: 129
    │               │   │   └── Node ID: 65
    │               │   │       ├── Node ID: 130
    │               │   │       └── Node ID: 131
    │               │   └── Node ID: 33
    │               │       ├── Node ID: 66
    │               │       │   ├── Node ID: 132
    │               │       │   └── Node ID: 133
    │               │       └── Node ID: 67
    │               │           ├── Node ID: 134
    │               │           └── Node ID: 135
    │               └── Node ID: 17
    │                   ├── Node ID: 34
    │                   │   ├── Node ID: 68
    │                   │   │   ├── Node ID: 136
    │                   │   │   └── Node ID: 137
    │                   │   └── Node ID: 69
    │                   │       ├── Node ID: 138
    │                   │       └── Node ID: 139
    │                   └── Node ID: 35
    │                       ├── Node ID: 70
    │                       │   ├── Node ID: 140
    │                       │   └── Node ID: 141
    │                       └── Node ID: 71
    │                           ├── Node ID: 142
    │                           └── Node ID: 143
    └── Node ID: 2
        ├── Node ID: 7
        │   ├── Node ID: 12
        │   │   ├── Node ID: 24
        │   │   │   ├── Node ID: 48
        │   │   │   │   ├── Node ID: 96
        │   │   │   │   │   ├── Node ID: 192
        │   │   │   │   │   └── Node ID: 193
        │   │   │   │   └── Node ID: 97
        │   │   │   │       ├── Node ID: 194
        │   │   │   │       └── Node ID: 195
        │   │   │   └── Node ID: 49
        │   │   │       ├── Node ID: 98
        │   │   │       │   ├── Node ID: 196
        │   │   │       │   └── Node ID: 197
        │   │   │       └── Node ID: 99
        │   │   │           ├── Node ID: 198
        │   │   │           └── Node ID: 199
        │   │   └── Node ID: 25
        │   │       ├── Node ID: 50
        │   │       │   ├── Node ID: 100
        │   │       │   │   ├── Node ID: 200
        │   │       │   │   └── Node ID: 201
        │   │       │   └── Node ID: 101
        │   │       │       ├── Node ID: 202
        │   │       │       └── Node ID: 203
        │   │       └── Node ID: 51
        │   │           ├── Node ID: 102
        │   │           │   ├── Node ID: 204
        │   │           │   └── Node ID: 205
        │   │           └── Node ID: 103
        │   │               ├── Node ID: 206
        │   │               └── Node ID: 207
        │   └── Node ID: 13
        │       ├── Node ID: 26
        │       │   ├── Node ID: 52
        │       │   │   ├── Node ID: 104
        │       │   │   │   ├── Node ID: 208
        │       │   │   │   └── Node ID: 209
        │       │   │   └── Node ID: 105
        │       │   │       ├── Node ID: 210
        │       │   │       └── Node ID: 211
        │       │   └── Node ID: 53
        │       │       ├── Node ID: 106
        │       │       │   ├── Node ID: 212
        │       │       │   └── Node ID: 213
        │       │       └── Node ID: 107
        │       │           ├── Node ID: 214
        │       │           └── Node ID: 215
        │       └── Node ID: 27
        │           ├── Node ID: 54
        │           │   ├── Node ID: 108
        │           │   │   ├── Node ID: 216
        │           │   │   └── Node ID: 217
        │           │   └── Node ID: 109
        │           │       ├── Node ID: 218
        │           │       └── Node ID: 219
        │           └── Node ID: 55
        │               ├── Node ID: 110
        │               │   ├── Node ID: 220
        │               │   └── Node ID: 221
        │               └── Node ID: 111
        │                   ├── Node ID: 222
        │                   └── Node ID: 223
        └── Node ID: 4
            ├── Node ID: 18
            │   ├── Node ID: 36
            │   │   ├── Node ID: 72
            │   │   │   ├── Node ID: 144
            │   │   │   └── Node ID: 145
            │   │   └── Node ID: 73
            │   │       ├── Node ID: 146
            │   │       └── Node ID: 147
            │   └── Node ID: 37
            │       ├── Node ID: 74
            │       │   ├── Node ID: 148
            │       │   └── Node ID: 149
            │       └── Node ID: 75
            │           ├── Node ID: 150
            │           └── Node ID: 151
            └── Node ID: 19
                ├── Node ID: 38
                │   ├── Node ID: 76
                │   │   ├── Node ID: 152
                │   │   └── Node ID: 153
                │   └── Node ID: 77
                │       ├── Node ID: 154
                │       └── Node ID: 155
                └── Node ID: 39
                    ├── Node ID: 78
                    │   ├── Node ID: 156
                    │   └── Node ID: 157
                    └── Node ID: 79
                        ├── Node ID: 158
                        └── Node ID: 159

320 nodes

└── Node ID: 0
    ├── Node ID: 1
    │   ├── Node ID: 6
    │   │   ├── Node ID: 10
    │   │   │   ├── Node ID: 20
    │   │   │   │   ├── Node ID: 40
    │   │   │   │   │   ├── Node ID: 80
    │   │   │   │   │   │   ├── Node ID: 160
    │   │   │   │   │   │   └── Node ID: 161
    │   │   │   │   │   └── Node ID: 81
    │   │   │   │   │       ├── Node ID: 162
    │   │   │   │   │       └── Node ID: 163
    │   │   │   │   └── Node ID: 41
    │   │   │   │       ├── Node ID: 82
    │   │   │   │       │   ├── Node ID: 164
    │   │   │   │       │   └── Node ID: 165
    │   │   │   │       └── Node ID: 83
    │   │   │   │           ├── Node ID: 166
    │   │   │   │           └── Node ID: 167
    │   │   │   └── Node ID: 21
    │   │   │       ├── Node ID: 42
    │   │   │       │   ├── Node ID: 84
    │   │   │       │   │   ├── Node ID: 168
    │   │   │       │   │   └── Node ID: 169
    │   │   │       │   └── Node ID: 85
    │   │   │       │       ├── Node ID: 170
    │   │   │       │       └── Node ID: 171
    │   │   │       └── Node ID: 43
    │   │   │           ├── Node ID: 86
    │   │   │           │   ├── Node ID: 172
    │   │   │           │   └── Node ID: 173
    │   │   │           └── Node ID: 87
    │   │   │               ├── Node ID: 174
    │   │   │               └── Node ID: 175
    │   │   └── Node ID: 11
    │   │       ├── Node ID: 22
    │   │       │   ├── Node ID: 44
    │   │       │   │   ├── Node ID: 88
    │   │       │   │   │   ├── Node ID: 176
    │   │       │   │   │   └── Node ID: 177
    │   │       │   │   └── Node ID: 89
    │   │       │   │       ├── Node ID: 178
    │   │       │   │       └── Node ID: 179
    │   │       │   └── Node ID: 45
    │   │       │       ├── Node ID: 90
    │   │       │       │   ├── Node ID: 180
    │   │       │       │   └── Node ID: 181
    │   │       │       └── Node ID: 91
    │   │       │           ├── Node ID: 182
    │   │       │           └── Node ID: 183
    │   │       └── Node ID: 23
    │   │           ├── Node ID: 46
    │   │           │   ├── Node ID: 92
    │   │           │   │   ├── Node ID: 184
    │   │           │   │   └── Node ID: 185
    │   │           │   └── Node ID: 93
    │   │           │       ├── Node ID: 186
    │   │           │       └── Node ID: 187
    │   │           └── Node ID: 47
    │   │               ├── Node ID: 94
    │   │               │   ├── Node ID: 188
    │   │               │   └── Node ID: 189
    │   │               └── Node ID: 95
    │   │                   ├── Node ID: 190
    │   │                   └── Node ID: 191
    │   └── Node ID: 3
    │       └── Node ID: 5
    │           ├── Node ID: 8
    │           │   ├── Node ID: 14
    │           │   │   ├── Node ID: 28
    │           │   │   │   ├── Node ID: 56
    │           │   │   │   │   ├── Node ID: 112
    │           │   │   │   │   │   ├── Node ID: 224
    │           │   │   │   │   │   └── Node ID: 225
    │           │   │   │   │   └── Node ID: 113
    │           │   │   │   │       ├── Node ID: 226
    │           │   │   │   │       └── Node ID: 227
    │           │   │   │   └── Node ID: 57
    │           │   │   │       ├── Node ID: 114
    │           │   │   │       │   ├── Node ID: 228
    │           │   │   │       │   └── Node ID: 229
    │           │   │   │       └── Node ID: 115
    │           │   │   │           ├── Node ID: 230
    │           │   │   │           └── Node ID: 231
    │           │   │   └── Node ID: 29
    │           │   │       ├── Node ID: 58
    │           │   │       │   ├── Node ID: 116
    │           │   │       │   │   ├── Node ID: 232
    │           │   │       │   │   └── Node ID: 233
    │           │   │       │   └── Node ID: 117
    │           │   │       │       ├── Node ID: 234
    │           │   │       │       └── Node ID: 235
    │           │   │       └── Node ID: 59
    │           │   │           ├── Node ID: 118
    │           │   │           │   ├── Node ID: 236
    │           │   │           │   └── Node ID: 237
    │           │   │           └── Node ID: 119
    │           │   │               ├── Node ID: 238
    │           │   │               └── Node ID: 239
    │           │   └── Node ID: 15
    │           │       ├── Node ID: 30
    │           │       │   ├── Node ID: 60
    │           │       │   │   ├── Node ID: 120
    │           │       │   │   │   ├── Node ID: 240
    │           │       │   │   │   └── Node ID: 241
    │           │       │   │   └── Node ID: 121
    │           │       │   │       ├── Node ID: 242
    │           │       │   │       └── Node ID: 243
    │           │       │   └── Node ID: 61
    │           │       │       ├── Node ID: 122
    │           │       │       │   ├── Node ID: 244
    │           │       │       │   └── Node ID: 245
    │           │       │       └── Node ID: 123
    │           │       │           ├── Node ID: 246
    │           │       │           └── Node ID: 247
    │           │       └── Node ID: 31
    │           │           ├── Node ID: 62
    │           │           │   ├── Node ID: 124
    │           │           │   │   ├── Node ID: 248
    │           │           │   │   └── Node ID: 249
    │           │           │   └── Node ID: 125
    │           │           │       ├── Node ID: 250
    │           │           │       └── Node ID: 251
    │           │           └── Node ID: 63
    │           │               ├── Node ID: 126
    │           │               │   ├── Node ID: 252
    │           │               │   └── Node ID: 253
    │           │               └── Node ID: 127
    │           │                   ├── Node ID: 254
    │           │                   └── Node ID: 255
    │           └── Node ID: 9
    │               ├── Node ID: 16
    │               │   ├── Node ID: 32
    │               │   │   ├── Node ID: 64
    │               │   │   │   ├── Node ID: 128
    │               │   │   │   │   ├── Node ID: 256
    │               │   │   │   │   └── Node ID: 257
    │               │   │   │   └── Node ID: 129
    │               │   │   │       ├── Node ID: 258
    │               │   │   │       └── Node ID: 259
    │               │   │   └── Node ID: 65
    │               │   │       ├── Node ID: 130
    │               │   │       │   ├── Node ID: 260
    │               │   │       │   └── Node ID: 261
    │               │   │       └── Node ID: 131
    │               │   │           ├── Node ID: 262
    │               │   │           └── Node ID: 263
    │               │   └── Node ID: 33
    │               │       ├── Node ID: 66
    │               │       │   ├── Node ID: 132
    │               │       │   │   ├── Node ID: 264
    │               │       │   │   └── Node ID: 265
    │               │       │   └── Node ID: 133
    │               │       │       ├── Node ID: 266
    │               │       │       └── Node ID: 267
    │               │       └── Node ID: 67
    │               │           ├── Node ID: 134
    │               │           │   ├── Node ID: 268
    │               │           │   └── Node ID: 269
    │               │           └── Node ID: 135
    │               │               ├── Node ID: 270
    │               │               └── Node ID: 271
    │               └── Node ID: 17
    │                   ├── Node ID: 34
    │                   │   ├── Node ID: 68
    │                   │   │   ├── Node ID: 136
    │                   │   │   │   ├── Node ID: 272
    │                   │   │   │   └── Node ID: 273
    │                   │   │   └── Node ID: 137
    │                   │   │       ├── Node ID: 274
    │                   │   │       └── Node ID: 275
    │                   │   └── Node ID: 69
    │                   │       ├── Node ID: 138
    │                   │       │   ├── Node ID: 276
    │                   │       │   └── Node ID: 277
    │                   │       └── Node ID: 139
    │                   │           ├── Node ID: 278
    │                   │           └── Node ID: 279
    │                   └── Node ID: 35
    │                       ├── Node ID: 70
    │                       │   ├── Node ID: 140
    │                       │   │   ├── Node ID: 280
    │                       │   │   └── Node ID: 281
    │                       │   └── Node ID: 141
    │                       │       ├── Node ID: 282
    │                       │       └── Node ID: 283
    │                       └── Node ID: 71
    │                           ├── Node ID: 142
    │                           │   ├── Node ID: 284
    │                           │   └── Node ID: 285
    │                           └── Node ID: 143
    │                               ├── Node ID: 286
    │                               └── Node ID: 287
    └── Node ID: 2
        ├── Node ID: 7
        │   ├── Node ID: 12
        │   │   ├── Node ID: 24
        │   │   │   ├── Node ID: 48
        │   │   │   │   ├── Node ID: 96
        │   │   │   │   │   ├── Node ID: 192
        │   │   │   │   │   └── Node ID: 193
        │   │   │   │   └── Node ID: 97
        │   │   │   │       ├── Node ID: 194
        │   │   │   │       └── Node ID: 195
        │   │   │   └── Node ID: 49
        │   │   │       ├── Node ID: 98
        │   │   │       │   ├── Node ID: 196
        │   │   │       │   └── Node ID: 197
        │   │   │       └── Node ID: 99
        │   │   │           ├── Node ID: 198
        │   │   │           └── Node ID: 199
        │   │   └── Node ID: 25
        │   │       ├── Node ID: 50
        │   │       │   ├── Node ID: 100
        │   │       │   │   ├── Node ID: 200
        │   │       │   │   └── Node ID: 201
        │   │       │   └── Node ID: 101
        │   │       │       ├── Node ID: 202
        │   │       │       └── Node ID: 203
        │   │       └── Node ID: 51
        │   │           ├── Node ID: 102
        │   │           │   ├── Node ID: 204
        │   │           │   └── Node ID: 205
        │   │           └── Node ID: 103
        │   │               ├── Node ID: 206
        │   │               └── Node ID: 207
        │   └── Node ID: 13
        │       ├── Node ID: 26
        │       │   ├── Node ID: 52
        │       │   │   ├── Node ID: 104
        │       │   │   │   ├── Node ID: 208
        │       │   │   │   └── Node ID: 209
        │       │   │   └── Node ID: 105
        │       │   │       ├── Node ID: 210
        │       │   │       └── Node ID: 211
        │       │   └── Node ID: 53
        │       │       ├── Node ID: 106
        │       │       │   ├── Node ID: 212
        │       │       │   └── Node ID: 213
        │       │       └── Node ID: 107
        │       │           ├── Node ID: 214
        │       │           └── Node ID: 215
        │       └── Node ID: 27
        │           ├── Node ID: 54
        │           │   ├── Node ID: 108
        │           │   │   ├── Node ID: 216
        │           │   │   └── Node ID: 217
        │           │   └── Node ID: 109
        │           │       ├── Node ID: 218
        │           │       └── Node ID: 219
        │           └── Node ID: 55
        │               ├── Node ID: 110
        │               │   ├── Node ID: 220
        │               │   └── Node ID: 221
        │               └── Node ID: 111
        │                   ├── Node ID: 222
        │                   └── Node ID: 223
        └── Node ID: 4
            ├── Node ID: 18
            │   ├── Node ID: 36
            │   │   ├── Node ID: 72
            │   │   │   ├── Node ID: 144
            │   │   │   │   ├── Node ID: 288
            │   │   │   │   └── Node ID: 289
            │   │   │   └── Node ID: 145
            │   │   │       ├── Node ID: 290
            │   │   │       └── Node ID: 291
            │   │   └── Node ID: 73
            │   │       ├── Node ID: 146
            │   │       │   ├── Node ID: 292
            │   │       │   └── Node ID: 293
            │   │       └── Node ID: 147
            │   │           ├── Node ID: 294
            │   │           └── Node ID: 295
            │   └── Node ID: 37
            │       ├── Node ID: 74
            │       │   ├── Node ID: 148
            │       │   │   ├── Node ID: 296
            │       │   │   └── Node ID: 297
            │       │   └── Node ID: 149
            │       │       ├── Node ID: 298
            │       │       └── Node ID: 299
            │       └── Node ID: 75
            │           ├── Node ID: 150
            │           │   ├── Node ID: 300
            │           │   └── Node ID: 301
            │           └── Node ID: 151
            │               ├── Node ID: 302
            │               └── Node ID: 303
            └── Node ID: 19
                ├── Node ID: 38
                │   ├── Node ID: 76
                │   │   ├── Node ID: 152
                │   │   │   ├── Node ID: 304
                │   │   │   └── Node ID: 305
                │   │   └── Node ID: 153
                │   │       ├── Node ID: 306
                │   │       └── Node ID: 307
                │   └── Node ID: 77
                │       ├── Node ID: 154
                │       │   ├── Node ID: 308
                │       │   └── Node ID: 309
                │       └── Node ID: 155
                │           ├── Node ID: 310
                │           └── Node ID: 311
                └── Node ID: 39
                    ├── Node ID: 78
                    │   ├── Node ID: 156
                    │   │   ├── Node ID: 312
                    │   │   └── Node ID: 313
                    │   └── Node ID: 157
                    │       ├── Node ID: 314
                    │       └── Node ID: 315
                    └── Node ID: 79
                        ├── Node ID: 158
                        │   ├── Node ID: 316
                        │   └── Node ID: 317
                        └── Node ID: 159
                            ├── Node ID: 318
                            └── Node ID: 319

... and so on. Balanced trees.