javascriptjavascript-objectstree-traversalpostorder

postorder traversal plain javascript


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.


Solution

  • 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.