Parse list and print all final paths

Question

Given lines with different indentation

orange
 blue
  yellow
  black
  white
 green

Print all final paths.

Expected output

orange/blue/yellow
orange/blue/black
orange/blue/white
orange/green

How to parse all lines(non binary tree) to print final(complete) paths?

Answer 1

The algorithm will use a stack:

Keep a stack of pairs, where each pair consists of a (partial) path and the indentation of its last part. Entries in the stack are always increasing by indentation. The stack starts empty.

For each line from the input, determine its indentation. As long as there are indents on the stack that are equal or greater, remove those pairs from the stack. Then get the path that's on top of the stack, append the current line to that path (without its indent, separated by /), pair it with the new indentation, and push that unto the stack. Output that path and repeat the process for the next input line.

Here is an implementation in JavaScript:

function getIndent(s) {
    return s.search(/\S/); // Index of first non-white-space character
}

function getPaths(text) {
    let stack = [];
    let paths = [];
    for (let line of text.split("\n")) {
        let indent = getIndent(line);
        while (stack.length > 0 && indent <= stack.at(-1).indent) {
            stack.pop();
        }
        let path = (stack.length > 0 ? stack.at(-1).path + "/" : "") + line.trim();
        stack.push({path, indent});
        paths.push(path);
    }
    return paths;
}

// Sample input
let text = 
`orange
 blue
  yellow
  black
  white
 green`;
 
for (let path of getPaths(text)) {
    console.log(path);
}