For example we have a JavaScript object which can contain other objects with arbitrary depth of nesting. Is it possible to traverse every element of this object not using recursion?

If not then what are minimum requirement for data structure to make it traversal using non-recursive iteration?

For example we have a JavaScript object which can contain other objects with arbitrary depth of nesting. Is it possible to traverse every element of this object not using recursion?

If not then what are minimum requirement for data structure to make it traversal using non-recursive iteration?

• javascript
• data-structures
• puter-science

• 6 You can change any recursion to a loop with a stack. – SLaks Commented Jan 21, 2015 at 16:45
• for in loop might be an answer: for(var i in obj){....} – Blauharley Commented Jan 21, 2015 at 16:50
• @SLaks thanks for pointing me toward the solution :) – Yevhen Kutishchev Commented Jan 21, 2015 at 17:06

2 Answers 2

As SLaks wrote above any recursion can be represented as loop with stack. So after thinking a while I came up with next solution:

var myobj = {
    one: "hello",
    two: "world",
    three: {
        one: 1,
        two: 2,
        three: 4,
        four: {
            one: true,
            two: false
        }
    },
    four: "!"
};

function traverse(obj) {
    var stack = [];

    stack.push(obj);

    while (stack.length) {
        for (var j in stack[0]) {
            if (typeof stack[0][j] === 'object') {
                stack.push(stack[0][j]);
            } else {
                console.log('%s: %s', j, stack[0][j]);
            }
        }
        stack.shift();
    }
}

traverse(myobj);

Traversing arbitrary object requires support for primitive types as well as plex types (including arrays), as well as protection against cyclic references. The following is a sample non recursive function that should traverse and stringify any object:

function FlatStringify( Arg )
{
   var ToString = '', ArgObject, Resume, nStartIndex, Stack = [], Processed = []

   do
   {
      if( Array.isArray( Arg ) )
      {
         var nIndex, nLen = Arg.length

         if( Resume )
         {
            nStartIndex = Resume[1] + 1
            ArgObject = Resume[2]
            Resume = undefined

            if( nStartIndex < nLen )
            {
               ToString += ', '
            }
         }
         else
         {
            if( Processed.indexOf( ArgObject ? ArgObject : Arg ) >= 0 )
            {
               ToString += '{ <cyclic>'
               nStartIndex = nLen
            }
            else
            {
               Processed.push( ArgObject ? ArgObject : Arg )
               nStartIndex = 0
               ToString += '{'
            }
         }

         nIndex = nStartIndex
         if( nIndex < nLen )
         {
            // Save our Array and loop position
            Stack.push( [ Arg, nIndex, ArgObject ] )

            // Restore Object Context if any!
            if( ArgObject )
            {
               ToString += ' ' + Arg[ nIndex ] + ': '
               Arg = ArgObject[ Arg[ nIndex ] ]
            }
            else
            {
               ToString += ' '
               Arg = Arg[ nIndex ]
            }

            nIndex++
         }

         if( nIndex >= nLen )
         {
            ToString += ' }'
            ArgObject = undefined
         }
         else
         {
            // Skip to the while( ... )
            continue
         }
      }
      else if( typeof Arg === 'object' )
      {
        if( Arg == null )
        {
           ToString += 'null'
        }
        else
        {
           ArgObject = Arg
           Arg = Object.keys( ArgObject )
           continue
        }
     }
     else if( typeof Arg === 'string' )
     {
        ToString += "'" + Arg + "'"
     }
     else if( typeof Arg === 'function' )
     {
        ToString += 'function ' +  Arg.name + '(){...}'
     }
     else if( typeof Arg === 'number' )
     {
        ToString += Arg
     }
     else if( typeof Arg === 'boolean' )
     {
        ToString += Arg
     }
     else
     {
        //console.log( typeof Arg )
        ToString += typeof Arg//String( Arg )
     }

     if( Stack.length )
     {
        //console.log( 'Resuming: ' + Stack.length + '(' + nLoops + ')' )
        Resume = Stack.pop()
        Arg = Resume[0]
     }
   }
   while( Resume || ArgObject || Stack.length )

   return ToString
}