CODEWITHSUNDEEP
javascriptarrays
Masha
Masha

Reputation: 857

javascript make recursive array walk and update some internal value (pointer)

I got the following array:

let arr = [
{
    children: [
        {
            children: [],
            current: true //pointer is at the first element with no children
        },
        {
            children: [
                {
                    children: [],
                    current: false  //if the pointer is here, next item should be the next parent`s first child (without children)
                },
                {
                    children: [
                               {
                                  current: false,
                                  children: []
                               },
                               {
                                current: false,
                                children: []
                               }
                              ],

                },
                {
                    children: [],
                    current: false 
                }               
            ]
        },
        {
            children: [],
            current: false
        },      
    ]

},
{
    children: [],
    current: false
},
{
    children: [],
    current: false
},
{
    children: [],
    current: false
},
];

I am creating an array walker (tree walker) so that the user could walk through it back and forth. So for example, when the user hits forward button, the pointer (current) moves to the next position among children in array, making this element current pointer false and next element current pointer true. If there is no more children in current parent, pointer moves to the next parent and makes current first child there (which does not have its children). User can only move among children which dont have their children (their children element is empty or there is no children at all), a parent with children cannot be selected and made current. My code is as follows:

makeNextQuestionCurrent = (arr, currentChanged = false) => {
    arr.some(
        (item, index) => {
            if(item.children && item.children.length > 1){
                if(!currentChanged){
                    this.makeNextQuestionCurrent(item.children);
                }
            }else{
                  if(item.current && !currentChanged){
                     item.current = false;
                     if(arr[index + 1]){      
                         arr[index + 1].current = true;
                                currentChanged  = true;
                     }else{
                           //some logic should be here...
                          }
                }
            }
        }
    );
}

So my problem begins when I reach the end of children of a parent. When the child is last, I cannot jump to next parent children. Any ideas how to fix it would be welcome. Thank you.

Upvotes: 0

Views: 364

Answers (1)

Inigo
Inigo

Reputation: 15030

I think you answered your own question:

So my problem begins when I reach the end of children of a parent. When the child is last, I cannot jump to next parent children.

You need a way to back up out of branches of the tree when you are done walking that branch. There are two ways you can do this:

  1. Add a pointer to each child pointing to its parent, OR
  2. Have your tree walker keep track of parents (and their parents) using a stack data structure.

You would go with option 1 if you want to maintain your current strategy of keeping your walking state within the tree itself. But this is a very bad idea:

  • It clutters up a data structure with program state that should be independent.
  • It results in complicated code, as yours is.
  • It is both memory and CPU inefficient.
  • It only allows one tree walker to operate at a time.

If you decide to disentangle your walker state from your tree data as I suggest, you can go with either option 1 or option 2.

Here is an implementation of an option 2 tree walker: 

class TreeWalker {
  currentNode
  currentChildIdx
  parentStack

  constructor (treeRoot) {
    this.currentNode = treeRoot
    this.currentChildIdx = -1
    this.parentStack = []
  }

  next () {
    // walk until a leaf node is found or we hit the end (terminal conditions are return stmts inside the loop)
    while (true) {
      const currentNode = this.currentNode
      const currentChildIdx = ++this.currentChildIdx
      if (currentNode.children && currentChildIdx < currentNode.children.length) {
        // we have more children; advance to the nex
        const child = currentNode.children[currentChildIdx]
        if (child.children) {
          // the next child itself has children; save state at this level, then descend
          this.parentStack.push({ node: currentNode, childIdx: currentChildIdx })
          this.currentNode = child
          this.currentChildIdx = -1
        } else {
          // the next child is a leaf; return it
          return child
        }
      } else if (this.parentStack.length > 0) {
        // no more children; back out to a parent.
        let p = this.parentStack.pop()
        this.currentNode = p.node
        this.currentChildIdx = p.childIdx
      } else {
        // back at root, all done
        return null
      }
    }
  }

  previous () {
    // I'll leave this one for you.
  }

}

TreeWalker assumes a consistent tree structure including having a root node that is the same structure as any other node. I does not store walk state in the tree, so current: was all removed.

let root = {
  val: 'branch a',
  children: [
    {
      val: 'leaf 1'
    },
    {
      val: 'branch b',
      children: [
        {
          val: 'leaf 2'
        }
      ]
    },
    {
      val: 'branch c',
      children: [
        {
          val: 'leaf 3'
        }
      ]
    }
  ]
}

I left some work for you: ;)

  • previous()
  • returning the root node if it is also a leaf node.

Upvotes: 1

Related Questions