//* Definition for a binary tree node.
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/**
 * @param {string} S
 * @return {TreeNode}
 */
class ParentStack {
    constructor() {
        this.length = 0
        this.head = null
    }
    push(val) {
        const node = new ParentNode(val)
        if (!this.head) {
            this.head = node
        } else {
            node.next = this.head
            this.head = node
        }
        this.length++
    }
    pop() {
        const node = this.head
        this.head = this.head.next
        this.length--
        return node.val
    }
    peek() {
        if (this.head) {
            return this.head.val
        } else {
            return null
        }
    }
}

class ParentNode {
    constructor(val) {
        this.val = val
        this.next = null
    }
}

var recoverFromPreorder = function(S) {
    var root

    const DASH = '-'

    const parentStack = new ParentStack()

    let i = 0
    while (i < S.length) {
        let char = S[i]
        let dashCount = 0
            // count dashes
        while (char === DASH && i < S.length) {
            dashCount++
            i++
            char = S[i]
        }
            // get all digits for int
        let charString = ''
            // check next chars until dash is found again
        while (char >= 0 && char < 10) { // check if char is a number
            charString = charString + char
                // check next char
            i++
            char = S[i]
        }
            // if dash count is greater than parent stack length, throw error
        if (dashCount > parentStack.length) {
            throw new Error('invalid input')
        }
            // pop parents to match dash count
        while (parentStack.length &&
               parentStack.length - dashCount > 0) {
            parentStack.pop()
        }
            // charString should be all digits for integer
            // next char will be dash now
            // make tree node from next index val
        let treeNode = new TreeNode(charString)
            // node = parent stack peek
        const parent = parentStack.peek()
            // if dash count is 0
            // and parent stack length is 0
            // make root for parent stack
        if (dashCount === 0 &&
           parentStack.length === 0) {
            root = new TreeNode(charString)
            parentStack.push(root)
            // if node's left has not been assigned
        } else if (!parent.left) {
                // add as node's left
            parent.left = treeNode
                // push to parent stack
            parentStack.push(treeNode)
        } else if (!parent.right) {
            // else if node's right has not been assigned
                // add as node's right
            parent.right = treeNode
                // push to parent stack
            parentStack.push(treeNode)
        } else {
            // else this parent has all nodes, check others
            parentStack.pop()
            i++
            continue
        }
    }

    return root
};