I want to ask for help in a task where I have to walk through a tree and get it as a result:
[ 4, 2, 5, 7, 6, 3, 1 ]
The class:
class Traversal {
postOrderTraversal(tree) {
// ...code here
}
}
My object :
const tree = {
value: 1,
children: [
{
value: 2,
children: [
{
value: 4,
children: []
}
],
},
{
value: 3,
children: [
{
value: 5,
children: [],
},
{
value: 6,
children: [
{
value: 7,
children: [],
},
],
},
],
},
],
};
Example illustration (we have a maximum of two children in each node):
+----------------+
| value: 1 |
+----------------+
/ \
/ \
+----------------+ +----------------+
| value: 2 | | value: 3 |
+----------------+ +----------------+
/ / \
/ / \
+----------------+ +----------------+ +----------------+
| value: 4 | | value: 5 | | value: 6 |
+----------------+ +----------------+ +----------------+
/
/
+----------------+
| value: 7 |
+----------------+
If anyone can help with this, please use plain javascript so I can better understand it.
I think using recursion is nice to demonstrate how post order is working. I found this to be a relatively straightforward solution.
class Traversal {
postOrderTraversal(tree, arr=[]) {
if(tree) {
this.postOrderTraversal(tree.children[0], arr);
this.postOrderTraversal(tree.children[1], arr);
arr.push(tree.value);
}
return arr;
}
}
Since your data set is that of a tree, I assume that children[0]
is considered to be the left node, and children[1]
is considered to be the right node.