postorder traversal plain javascript

Question

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.

Answer 1

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.

Answer 2

This is probably the easiest implementation I can come up with. Given just two lines of code, there's very little room for explanation -

function *postorder(t) {
  for (child of t.children) yield *postorder(child)
  yield t.value
}

const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]}

console.log(Array.from(postorder(mytree)))

[4,2,5,7,6,3,1]

Confounding traversal with classes, though possible, serves no benefit to you. postorder remains unchanged -

function *postorder(t) {
  for (child of t.children) yield *postorder(child)
  yield t.value
}

class Traversal {
  postorder(t) { return Array.from(postorder(t)) }
}

const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]}

const q = new Traversal()

console.log(q.postorder(mytree))

Compare with preorder. The only change necessary to achieve this traversal is to switch the order of the two lines -

function *preorder(t) {
  yield t.value
  for (child of t.children) yield *preorder(child)
}

const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]}

console.log(Array.from(preorder(mytree)))

[1,2,4,3,5,6,7]

Answer 3

As is often the case with these sorts of tree-visiting algorithms, your best bet lies with recursion: Each node in the tree should return its own value, after the values of its children. There are certainly shorter and more efficient ways to do this than what I have written below, but I have structured the code in such a way that it is clear when the recursion terminates (the current node has no children) and in which order the values are added to the returned array for ease of understanding.

function postOrderTraversal(node) {
  if (node.children.length === 0) {
    return [node.value];
  } else {
    var arr = [];
    for (var i = 0; i < node.children.length; i++) {
      var childValues = postOrderTraversal(node.children[i]);
      arr = arr.concat(childValues);
    }
    arr.push(node.value);
    return arr;
  }
}