breaking out of multiple recursion based on a value that changes during the recursion

user_2054671 0
Viewed 79

EDIT: Apart from other solutions to this problem, I am also keen to understand if this kind of recursion or recursive problems have a pattern, is there a name to the technique that i have used (i.e. to pass in an object by reference to break future recursion based on changes to the object) ? Is this technique useful in some other scenarios?

I am looking for a value in a nAry tree, and once it is found i want to break the recursion (there are other base cases to break the example). This is what the code looks like:

function getCommentById(root, commentId, foundComment) {
  if (root.id === commentId) {
    return root;
  }

  if (foundComment.comment) {
    return foundComment.comment;
  }

  if (!root.comments) {
    return foundComment.comment;
  } else {
    for (let i = 0; i < root.comments.length; i++) {
      foundComment.comment = getCommentById(
        root.comments[i],
        commentId,
        foundComment
      );
    }
  }

  return foundComment.comment;
}

basically i am looking through nested comments to find a comment by its id.

I have to iterate through all the children of the current comment and call this function recursively. Let's say I found the comment in child1 of the current comment, I would like to not recurse any further and just break out of the recursion, but the loop would continue to the next sibling and recurse. This kind of thing was easy in binary tree as i could just do something like

return getCommentById(left) || getCommentById(right)

but i was having trouble implementing the same logic here because we would need to somehow store the result of each children call, and based on that decide whether or not we have found the value. So my solution uses a auxiliary variable which denotes when the value has been found. I figured out that this needs to be an object and not a variable, so that the value change is visible in subsequent recursion call from child1 to child2. This wouldn't have been possible if i had just used a flag and set it to true in child1 recursion, because then child2 recursion would still see the flag as false and keep on recursing.

Is there a better approach? Is there a name for this technique of using object reference to break the recursion? How else can this be implemented?

EDIT: dataset for testing

const post = {
id: "post1",
title: "Sample Post 1",
description: "This is a sample post",
createdBy: "user1",
createdAt: new Date(),
comments: [
  {
    id: "post1comment1",
    text: "This is comment 1",
    userId: "user1",
    timestamp: new Date().setFullYear(2018),
    comments: [
      {
        id: "post1comment1.1",
        text: "This is sub comment 1 of comment 1",
        userId: "user2",
        timestamp: new Date()
      }
    ]
  },
  {
    id: "post1comment2",
    text: "This is comment 2",
    userId: "user4",
    timestamp: new Date()
  },
  {
    id: "post1comment3",
    text: "This is comment 3",
    userId: "user4",
    timestamp: new Date()
  }
]
  },

usage:

const foundComment = { comment: null };
getCommentById(post, "post1comment1.1", foundComment);
tree recursion javascript
3 Answers

You could use an iterative stack-based tree traversal approach. Here is the basic idea:

function find_thing(root) {
  var stack = [ root ];
  
  while(0 < stack.length) {
     var current_thing = stack.pop();
     if(is_the_thing(current_thing)) {
       return current_thing;
     }
     
     stack = stack.concat(current_thing.AllMyKids());
  }

  return null;
}

user_5008900

You could take the node directly as result without returning it back via object reference.

function getCommentById(root, commentId) {
    var temp;

    if (root.id === commentId) return root;
    (root.comments || []).some(node => temp = getCommentById(node, commentId))
    return temp;
}

const
    post = { id: "post1", title: "Sample Post 1", description: "This is a sample post", createdBy: "user1", createdAt: new Date(), comments: [{ id: "post1comment1", text: "This is comment 1", userId: "user1", timestamp: new Date().setFullYear(2018), comments: [{ id: "post1comment1.1", text: "This is sub comment 1 of comment 1", userId: "user2", timestamp: new Date() }] }, { id: "post1comment2", text: "This is comment 2", userId: "user4", timestamp: new Date() }, { id: "post1comment3", text: "This is comment 3", userId: "user4", timestamp: new Date() }] },
    result = getCommentById(post, "post1comment1.1");

console.log(result);

user_14476750

Adding this for completeness. Based on a better understanding of the problem i was trying to solve, I was able to reduce my code to this:

function getCommentByIdSimple(root, commentId) {
  if (!root) {
    return null;
  }

  if (root.id === commentId) {
    return root;
  } else {
    let node;
    if (!root.comments) {
      return null;
    }
    for (let i = 0; i < root.comments.length; i++) {
      if ((node = getCommentByIdSimple(root.comments[i], commentId))) {
        return node;
      }
    }
  }

  return null;
}

The problem i was trying to solve was how to exit the for loop once i have found the desired comment. In the above implementation I check if node is found i just return node, so further iterations after the return are ignored.

This approach was inspired from: n-ary tree searching function

user_20546710
Related