Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Welcome to Software Development on Codidact!

Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.

Post History

77%
+5 −0
Q&A How this recursive treewalker works?

To understand the concept of recursive tree traversal, I would like to give you an analogy. Imagine a labyrinth of rooms connected like a tree structure. That is, there is an entry to the first r...

posted 2y ago by Dirk Herrmann‭  ·  edited 2y ago by Dirk Herrmann‭

Answer
#3: Post edited by user avatar Dirk Herrmann‭ · 2022-04-29T19:04:47Z (over 2 years ago)
Added the sticky notes to be able to represent variables on the stack.
  • To understand the concept of recursive tree traversal, I would like to give you an analogy. Imagine a labyrinth of rooms connected like a tree structure. That is, there is an entry to the first room, and when entering a room you may find doors leading into rooms deeper down into the labyrinth, but it is guaranteed that there are no cycles.
  • Some rooms only have an entry, but don't lead to further rooms (leaves of the tree). Of these, some have walls that are painted blue and some of these have walls that are painted green.
  • Your task is to go through all rooms and paint the blue ones and only the blue ones yellow. With you, you take a rope that will always show you the way back to the entrance of the labyrinth. Or, in other words, when you are in one room, the rope will show you how to get back to the room from where you entered the current room.
  • Your algorithm would start by entering the labyrinth, that is, go into the first room. From then on, you will do the following:
  • After entering a room:
  • if it has blue walls:
  • paint the blue walls yellow
  • otherwise:
  • for each door (from left to right), if any, leading to a new room:
  • enter that door and follow these instructions again.
  • use the rope to return to the room from where you came
  • This algorithm is just a translation of your tree-traversal: A node in the tree that is a `TEXT_NODE` is known to be a leaf of the tree and it contains text to be replaced. This corresponds to the rooms with the blue walls: We know that there are no further rooms from such a room, but we know we have to do the painting here.
  • Any other node may or may not have child nodes (there are other leaf nodes than `TEXT_NODE`s, but their list of children is just empty). That is, if there are child nodes, for each child node move there and do just the same thing again. Now, look at the labyrinth analogy: The non-bluish rooms may be the green ones (from which no doors lead further), or just other rooms from which you can move into further rooms deeper down the labyrinth.
  • Finally, the rope: The rope always brings you back to the room from which you entered the current room. Following the rope back corresponds to returning from the innermost recursive function call. When your program is executed, the rope is the computer stack.
  • To understand the concept of recursive tree traversal, I would like to give you an analogy. Imagine a labyrinth of rooms connected like a tree structure. That is, there is an entry to the first room, and when entering a room you may find doors leading into rooms deeper down into the labyrinth, but it is guaranteed that there are no cycles.
  • Some rooms only have an entry, but don't lead to further rooms (leaves of the tree). Of these, some have walls that are painted blue and some of these have walls that are painted green.
  • Your task is to go through all rooms and paint the blue ones and only the blue ones yellow. With you, you take a rope that will always show you the way back to the entrance of the labyrinth. Or, in other words, when you are in one room, the rope will show you how to get back to the room from where you entered the current room. In addition to the rope you have some pen and lots of fresh sticky note sheets with you.
  • Your algorithm would start by entering the labyrinth, that is, go into the first room. From then on, you will do the following:
  • After entering a room:
  • take a fresh sheet from your sticky notes and stick it to a wall
  • if the room has blue walls:
  • paint the blue walls yellow
  • otherwise:
  • for each door (from left to right), if any, leading to a new room:
  • write to the sticky note which is the next door to enter
  • enter that door and follow these instructions again.
  • as you are now done with this room, dispose of the sticky note
  • use the rope to return to the room from where you came
  • This algorithm is just a translation of your tree-traversal: A node in the tree that is a `TEXT_NODE` is known to be a leaf of the tree and it contains text to be replaced. This corresponds to the rooms with the blue walls: We know that there are no further rooms from such a room, but we know we have to do the painting here.
  • Any other node may or may not have child nodes (there are other leaf nodes than `TEXT_NODE`s, but their list of children is just empty). That is, if there are child nodes, for each child node move there and do just the same thing again. Now, look at the labyrinth analogy: The non-bluish rooms may be the green ones (from which no doors lead further), or just other rooms from which you can move into further rooms deeper down the labyrinth.
  • Finally, the sticky notes and the rope: These two represent the computer stack. Each sticky note is for data (variables) in the current room (the current depth of recursion): You get a fresh sticky note on entering the room, as you get a new set of local variables with each recursive call. The rope always brings you back to the room from which you entered the current room. Following the rope back corresponds to returning from the innermost recursive function call.
#2: Post edited by user avatar Dirk Herrmann‭ · 2022-04-28T23:20:06Z (over 2 years ago)
  • To understand the concept of recursive tree traversal, I would like to give you an analogy. Imagine a labyrinth of rooms connected like a tree structure. That is, there is an entry to the first room, and when entering a room you may find doors leading into rooms deeper down into the labyrinth, but it is guaranteed that there are no cycles.
  • Some rooms only have an entry, but don't lead to further rooms (leaves of the tree). Of these, some have walls that are painted blue and some of these have walls that are painted green.
  • Your task is, to go through all rooms and paint the blue ones and only the blue ones yellow. With you, you take a rope that will always show you the way back to the entrance of the labyrinth. Or, in other words, when you are in one room, the rope will show you how to get back to room from where you entered this room.
  • Your algorithm would start by entering the labyrinth, that is, go into the first room. From then on, you will do the following:
  • After entering a room:
  • if it has blue walls:
  • paint the blue walls yellow
  • otherwise:
  • for each door (from left to right), if any, leading to a new room:
  • enter that door and follow these instructions again.
  • use the rope to return to the room from where you came
  • This algorithm is just a translation of your tree-traversal: A node in the tree that is a `TEXT_NODE` is known to be a leaf of the tree and it contains text to be replaced. This corresponds to the rooms with the blue walls: We know that there are no further rooms from such a room, but we know we have to do the painting here.
  • Any other node may or may not have child nodes (there are other leaf nodes than `TEXT_NODE`s, but their list of children is just empty). That is, if there are child nodes, for each child node move there and do just the same thing again. Now, look at the labyrinth analogy: The non-bluish rooms may be the green ones (from which no doors lead further), or just other rooms from which you can move into further rooms deeper down the labyrinth.
  • Finally, the rope: The rope always brings you back to the room from which you entered the current room. Following the rope back corresponds to returning from the innermost recursive function call. When your program is executed, the rope is the computer stack.
  • To understand the concept of recursive tree traversal, I would like to give you an analogy. Imagine a labyrinth of rooms connected like a tree structure. That is, there is an entry to the first room, and when entering a room you may find doors leading into rooms deeper down into the labyrinth, but it is guaranteed that there are no cycles.
  • Some rooms only have an entry, but don't lead to further rooms (leaves of the tree). Of these, some have walls that are painted blue and some of these have walls that are painted green.
  • Your task is to go through all rooms and paint the blue ones and only the blue ones yellow. With you, you take a rope that will always show you the way back to the entrance of the labyrinth. Or, in other words, when you are in one room, the rope will show you how to get back to the room from where you entered the current room.
  • Your algorithm would start by entering the labyrinth, that is, go into the first room. From then on, you will do the following:
  • After entering a room:
  • if it has blue walls:
  • paint the blue walls yellow
  • otherwise:
  • for each door (from left to right), if any, leading to a new room:
  • enter that door and follow these instructions again.
  • use the rope to return to the room from where you came
  • This algorithm is just a translation of your tree-traversal: A node in the tree that is a `TEXT_NODE` is known to be a leaf of the tree and it contains text to be replaced. This corresponds to the rooms with the blue walls: We know that there are no further rooms from such a room, but we know we have to do the painting here.
  • Any other node may or may not have child nodes (there are other leaf nodes than `TEXT_NODE`s, but their list of children is just empty). That is, if there are child nodes, for each child node move there and do just the same thing again. Now, look at the labyrinth analogy: The non-bluish rooms may be the green ones (from which no doors lead further), or just other rooms from which you can move into further rooms deeper down the labyrinth.
  • Finally, the rope: The rope always brings you back to the room from which you entered the current room. Following the rope back corresponds to returning from the innermost recursive function call. When your program is executed, the rope is the computer stack.
#1: Initial revision by user avatar Dirk Herrmann‭ · 2022-04-28T23:17:51Z (over 2 years ago)
To understand the concept of recursive tree traversal, I would like to give you an analogy.  Imagine a labyrinth of rooms connected like a tree structure.  That is, there is an entry to the first room, and when entering a room you may find doors leading into rooms deeper down into the labyrinth, but it is guaranteed that there are no cycles.

Some rooms only have an entry, but don't lead to further rooms (leaves of the tree).  Of these, some have walls that are painted blue and some of these have walls that are painted green.

Your task is, to go through all rooms and paint the blue ones and only the blue ones yellow.  With you, you take a rope that will always show you the way back to the entrance of the labyrinth.  Or, in other words, when you are in one room, the rope will show you how to get back to room from where you entered this room.

Your algorithm would start by entering the labyrinth, that is, go into the first room.  From then on, you will do the following:

    After entering a room:
        if it has blue walls:
            paint the blue walls yellow
        otherwise:
            for each door (from left to right), if any, leading to a new room:
                 enter that door and follow these instructions again.
        use the rope to return to the room from where you came

This algorithm is just a translation of your tree-traversal: A node in the tree that is a `TEXT_NODE` is known to be a leaf of the tree and it contains text to be replaced.  This corresponds to the rooms with the blue walls: We know that there are no further rooms from such a room, but we know we have to do the painting here.

Any other node may or may not have child nodes (there are other leaf nodes than `TEXT_NODE`s, but their list of children is just empty).  That is, if there are child nodes, for each child node move there and do just the same thing again.  Now, look at the labyrinth analogy: The non-bluish rooms may be the green ones (from which no doors lead further), or just other rooms from which you can move into further rooms deeper down the labyrinth.

Finally, the rope: The rope always brings you back to the room from which you entered the current room.  Following the rope back corresponds to returning from the innermost recursive function call.  When your program is executed, the rope is the computer stack.