Traversing tree by LEVEL

Question

I have the json tree below.

interface Tree {
    v: number, // value
    c: Tree[], // children
}

const tree: Tree = {
    v: 0, c: [
        {
            v: 1,
            c: [
                {
                    v: 4,
                    c: [
                        {
                            v: 9, c: [],
                        }
                    ],
                },
                {
                    v: 5,
                    c: [
                        {
                            v: 10, c: [],
                        }
                    ],
                },
            ],
        },
        {
            v: 2,
            c: [
                {
                    v: 6,
                    c: [
                        {
                            v: 11, c: [],
                        }
                    ],
                },
                {
                    v: 7,
                    c: [
                        {
                            v: 12, c: [],
                        }
                    ],
                }
            ],
        },
        {
            v: 3,
            c: [
                {
                    v: 8,
                    c: [
                        {
                            v: 13, c: [],
                        },
                        {
                            v: 14, c: [],
                        },
                    ]
                }
            ],
        },
    ]
}

How to traverse the tree by Level?

In other words, if the applied function on each node is just console.log

The above input should print 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14

or even better, we can print by level and the output would be:

Level 0: [0]
Level 1: [1,2,3]
LeveL 2: [4,5,6,7,8]
Level 3: [9,10,11,12,13,14]

Failed Attempt

function walkTree(t){
        console.log(t.v);
        for(const child of t.c){
            walkTree(child)
        }
}

recursive function I tried. But it traverse by branch not level — TSR, Sep 11 '20 at 22:13
Show us the recursive function. It should be the right approach, but it might be your implementation that fails. — Emiel Zuurbier, Sep 11 '20 at 22:17
`function walkTree(t){ console.log(t.v); for(const child of t.c){ walkTree(child) } }` — TSR, Sep 11 '20 at 22:20

score 1 · Accepted Answer · answered Sep 11 '20 at 22:43

You'll need to store all the values from each level in an array and pass that array down with each level you go through. Then return that array at the end so it goes back up. This is how you'll get the structure you are looking for.

Then loop through the result and log the text with the values.

See example below.

const tree = {
    v: 0, 
    c: [
        {
            v: 1,
            c: [
                {
                    v: 4,
                    c: [
                        {
                            v: 9, c: [],
                        }
                    ],
                },
                {
                    v: 5,
                    c: [
                        {
                            v: 10, c: [],
                        }
                    ],
                },
            ],
        },
        {
            v: 2,
            c: [
                {
                    v: 6,
                    c: [
                        {
                            v: 11, c: [],
                        }
                    ],
                },
                {
                    v: 7,
                    c: [
                        {
                            v: 12, c: [],
                        }
                    ],
                }
            ],
        },
        {
            v: 3,
            c: [
                {
                    v: 8,
                    c: [
                        {
                            v: 13, c: [],
                        },
                        {
                            v: 14, c: [],
                        },
                    ]
                }
            ],
        },
    ]
}

function walkTree(tree, level = 0, collection = []) {

  // Select the values from this level.
  const { c, v } = tree;
  
  // Create an array for this level if it doesn't have one.
  if (!Array.isArray(collection[level])) {
    collection[level] = [];
  }
  
  // Store the value of this level in the array.
  collection[level].push(v);
  
  // Loop over sub levels and pass the collection down while incrementing the level.
  for (const subTree of c) {
    collection = walkTree(subTree, level + 1, collection);
  }
  
  // Return collection at each level.
  return collection;
}

// Start walking.
const result = walkTree(tree);

result.forEach((value, index) => {
  console.log(`Level ${index}:`, value);
});

score 0 · Answer 2 · answered Jan 02 '21 at 18:50

Here is an iterative solution using object-scan

One advantage is that you get access to meta information in filterFn, so it makes it easy to do other processing. However there is obviously a trade-off in introducing a dependency.

// const objectScan = require('object-scan');

const myTree = { v: 0, c: [{ v: 1, c: [{ v: 4, c: [{ v: 9, c: [] }] }, { v: 5, c: [{ v: 10, c: [] }] }] }, { v: 2, c: [{ v: 6, c: [{ v: 11, c: [] }] }, { v: 7, c: [{ v: 12, c: [] }] }] }, { v: 3, c: [{ v: 8, c: [{ v: 13, c: [] }, { v: 14, c: [] }] }] }] };

const byLevel = (tree) => objectScan(['**'], {
  filterFn: ({ isLeaf, key, value, context }) => {
    if (isLeaf) {
      const level = (key.length - 1) / 2;
      if (!(level in context)) {
        context[level] = [];
      }
      context[level].push(value);
    }
  }
})(tree, []);

console.log(byLevel(myTree));
/* =>
[ [ 0 ],
  [ 3, 2, 1 ],
  [ 8, 7, 6, 5, 4 ],
  [ 14, 13, 12, 11, 10, 9 ] ]
*/

.as-console-wrapper {max-height: 100% !important; top: 0}

<script src="https://bundle.run/object-scan@13.7.1"></script>

Disclaimer: I'm the author of object-scan

score 0 · Answer 3 · answered Jan 02 '21 at 23:33

Since this was brought back up...

A fairly simple breadth-first scan of your tree might look like this:

const breadthFirst = (tree, xs = [].concat(tree)) => 
  xs.length == 0 
    ? [] 
    : [xs .map (x => x.v), ... breadthFirst (xs. flatMap (x => x.c))]
  
const tree = {v: 0, c: [{v: 1, c: [{v: 4, c: [{v: 9, c: []}]}, {v: 5, c: [{v: 10, c: []}]}]}, {v: 2, c: [{v: 6, c: [{v: 11, c: []}]}, {v: 7, c: [{v: 12, c: []}]}]}, {v: 3, c: [{v: 8, c: [{v: 13, c: []}, {v: 14, c: []}]}]}]}

console .log (breadthFirst (tree))

This recursive function accepts an array of nodes (and if you supply just one wraps an array around it) and then if that array is empty, returns an empty array, otherwise, returns an array containing an array of the v properties of each node followed by all the results of a recursive call using the array of children of each node.

That gives us a result like

[[0], [1, 2, 3], [4, 5, 6, 7, 8], [9, 10, 11, 12, 13, 14]]

But if you would prefer

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

You can do it with this minor alteration:

const breadthFirst = (tree, xs = [].concat(tree)) => 
  xs.length == 0 
    ? [] 
    : [...xs .map (x => x.v), ... breadthFirst (xs. flatMap (x => x.c))]

Finally, there are some arguments against using default parameters. If you want your function to be as widely useful as possible -- as if, for instance, you're publishing a public library -- then it might be worth removing these default parameters by adding a wrapper function:

const levels = (xs) => 
  xs.length == 0 
    ? [] 
    : [xs .map (x => x.v), ... levels (xs. flatMap (x => x.c))]

const breadthFirst = (tree) =>
  levels ([tree])

Traversing tree by LEVEL

3 Answers3