0

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.

Improve this question
9
  • What you're showing is a tree, that you implemented using arrays. If you're having trouble writing a tree walker, my first recommendation would be to pick a better data structure: use an actual tree, so that calling a function on a node will respond either directly or delegate the response by calling one (or more of) its own child(ren). Where does the data you're showing come from? (e.g. did you make it do that, or is that data you don't control). Commented Apr 17, 2020 at 15:02
  • thank you for comment. could you provide an example of such tree data structure? may be there is some example of such tree walker? Commented Apr 17, 2020 at 15:15
  • It kind of depends: is this homework, or are you working on your own project, or are you doing paid work and this is part of it? Because the answer to your question is radically different between those three. Commented Apr 17, 2020 at 15:18
  • its a project, there is a list of topics with back and forward buttons for user to navigate among them Commented Apr 17, 2020 at 15:21
  • Then the answer is "this is called depth-first tree traversal", so with those terms, google and SO will find you what you're looking for. In fact, you probably just want to read through stackoverflow.com/questions/48612674/… and then if you have more questions, web searching should now work fine, since you now know what words to look for. Commented Apr 17, 2020 at 15:27

1 Answer 1

Reset to default
1

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.
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.