I need help with specific implementation of iterative depth first traversal algorithm. I have an object like this (it's just an example, object might have more properties and be deeper nested):

const root = {
  a: 1,
  b: {
    c: {
      d: {
        e: 2,
        f: 3,
      }
    },
    g: [
      {
        h: 4,
        i: 5,
      },
      {
        j: 6,
        k: 7,
      }
    ]
  }
}

What I need is a function that would traverse the whole object and return an array like this:

[
  {"a": 1},
  {"b.c.d.e": 2},
  {"b.c.d.f": 3},
  {"b.g.0.h": 4},
  {"b.g.0.i": 5},
  {"b.g.1.j": 6},
  {"b.g.1.k": 7},
]

I managed to create an algorithm that sort of solves my problem, but needs one additional step in the end. Result of the algorithm is an array of strings like that:

[
  'a^1',
  'b.c.d.e^2',
  'b.c.d.f^3',
  'b.g.0.h^4',
  'b.g.0.i^5',
  'b.g.1.j^6',
  'b.g.1.k^7'
]

so in order to achieve what I want I have to do one full iteration over the result of my algorithm, split strings by ^ symbol and then create objects based on that.

This is the part that I need help with - how can I improve/change my solution so I don't need to do that last step?

function dft(root) {
  let stack = [];
  let result = [];
  const isObject = value => typeof value === "object";
  stack.push(root);
  while (stack.length > 0) {
    let node = stack.pop();
    if (isObject(node)) {
      Object.entries(node).forEach(([childNodeKey, childNodeValue]) => {
        if (isObject(childNodeValue)) {
          const newObject = Object.fromEntries(
            Object.entries(childNodeValue).map(([cnk, cnv]) => {
              return [`${childNodeKey}.${cnk}`, cnv];
            })
          );
          stack.push(newObject);
        } else {
          stack.push(`${childNodeKey}^${childNodeValue}`);
        }
      })
    } else {
      result.push(node);
    }
  }
  return result.reverse();
}

CodePudding user response：

I'd keep pairs <keys,value> in the stack and only create a string key when storing a newly created object:

function dft(obj) {
    let stack = []
    let res = []

    stack.push([[], obj])

    while (stack.length) {
        let [keys, val] = stack.pop()

        if (!val || typeof val !== 'object') {
            res.push({
                [keys.join('.')]: val
            })
        } else {
            Object.entries(val).forEach(p => stack.push([
                keys.concat(p[0]),
                p[1],
            ]))
        }
    }

    return res.reverse()
}

//

const root = {
  a: 1,
  b: {
    c: {
      d: {
        e: 2,
        f: 3,
      }
    },
    g: [
      {
        h: 4,
        i: 5,
      },
      {
        j: 6,
        k: 7,
      }
    ]
  }
}

console.log(dft(root))

CodePudding user response：

You can push the childNodeKey childNodeValue pair directly as an object to your result array.

Change

stack.push(`${childNodeKey}^${childNodeValue}`);

to

const newEntry = {}
newEntry[childNodeKey] = childNodeValue
result.push(newEntry);

or with ES2015 syntax (you would need a transpiler for browser compatibility)

result.push({[childNodeKey]: childNodeValue});

Complete function:

const root = {
  a: 1,
  b: {
    c: {
      d: {
        e: 2,
        f: 3,
      }
    },
    g: [
      {
        h: 4,
        i: 5,
      },
      {
        j: 6,
        k: 7,
      }
    ]
  }
}

function dft(root) {
  let stack = [];
  let result = [];
  const isObject = value => typeof value === "object";
  stack.push(root);
  while (stack.length > 0) {
    let node = stack.pop();
    if (isObject(node)) {
      Object.entries(node).forEach(([childNodeKey, childNodeValue]) => {
        if (isObject(childNodeValue)) {
          const newObject = Object.fromEntries(
            Object.entries(childNodeValue).map(([cnk, cnv]) => {
              return [`${childNodeKey}.${cnk}`, cnv];
            })
          );
          stack.unshift(newObject);
        } else {
          const newEntry = {}
          newEntry[childNodeKey] = childNodeValue
          result.push({[childNodeKey]: childNodeValue});
        }
      })
    } else {
      result.push(node);
    }
  }
  return result;
}

console.log(dft(root))

CodePudding user response：

As you mentioned, you almost got it complete. Just make the array entry an object just before pushing it into result. By splitting Array.prototype.split('^') you can get 'b.g.0.h^4' >>> ['b.g.0.h', '4']. So, rest is a cake:

if (isObject(node)) {
 ...
} else {
  const keyAndValue = node.split('^')
  // approach 1)
  // const key = keyAndValue[0]
  // const value = keyAndValue[1]
  // dynamic key setting
  // result.push({[key]: value});

  // approach 2)
  // or in short,
  // dynamic key setting
  result.push({[keyAndValue[0]]: keyAndValue[1]});
}

CodePudding user response：

You could use a stack where each item has an iterator over the children, and the path up to that point:

function collect(root) {
    const Node = (root, path) => 
        ({ iter: Object.entries(root)[Symbol.iterator](), path });
    const result = [];
    const stack = [Node(root, "")];
    while (stack.length) {
        const node = stack.pop();
        const {value} = node.iter.next();
        if (!value) continue;
        stack.push(node);
        const [key, child] = value;
        const path = node.path ? node.path   "."   key : key;
        if (Object(child) !== child) result.push({ [path]: child });
        else stack.push(Node(child, path));
    }
    return result;
}

const root = {a:1,b:{c:{d:{e:2,f:3}},g:[{h:4,i:5},{j:6,k:7}]}};
console.log(collect(root));