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

Dirk Herrmann‭ · 2022-04-29T19:04:47Z (almost 2 years ago)
Added the sticky notes to be able to represent variables on the stack.

Copy Link

Raw

Markdown

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

Dirk Herrmann‭ · 2022-04-28T23:20:06Z (almost 2 years ago)

Copy Link

Raw

Markdown

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

Dirk Herrmann‭ · 2022-04-28T23:17:51Z (almost 2 years ago)

Copy Link

Raw

Markdown

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.

Communities

Post History