DEV Community

Cover image for 590. N-ary Tree Postorder Traversa
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

590. N-ary Tree Postorder Traversa

590. N-ary Tree Postorder Traversa

Difficulty: Easy

Topics: Stack, Tree, Depth-First Search

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Example 1:

narytreeexample

  • Input: root = [1,null,3,2,4,null,5,6]
  • Output: [5,6,3,2,4,1]

Example 2:

sample_4_964

  • Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
  • Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Constraints:

  • The number of the nodes in the tree is in the range [0, 1004].
  • -100 <= Node.val <= 1004
  • The height of the n-ary tree is less than or equal to 1000.

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution:

We can approach it both recursively and iteratively. Since the follow-up asks for an iterative solution, we'll focus on that. Postorder traversal means visiting the children nodes first and then the parent node.

Let's implement this solution in PHP: 590. N-ary Tree Postorder Traversal

<?php
//Definition for a Node.
class Node {
    public $val = null;
    public $children = [];

    public function __construct($val) {
        $this->val = $val;
    }
}

/**
 * @param Node $root
 * @return integer[]
 */
function postorder($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
$root1 = new Node(1);
$root1->children = [
    $node3 = new Node(3),
    new Node(2),
    new Node(4)
];
$node3->children = [
    new Node(5),
    new Node(6)
];

print_r(postorder($root1)); // Output: [5, 6, 3, 2, 4, 1]

// Example 2:
$root2 = new Node(1);
$root2->children = [
    new Node(2),
    $node3 = new Node(3),
    $node4 = new Node(4),
    $node5 = new Node(5)
];
$node3->children = [
    $node6 = new Node(6),
    $node7 = new Node(7)
];
$node4->children = [
    $node8 = new Node(8)
];
$node5->children = [
    $node9 = new Node(9),
    $node10 = new Node(10)
];
$node7->children = [
    new Node(11)
];
$node8->children = [
    new Node(12)
];
$node9->children = [
    new Node(13)
];
$node11 = $node7->children[0];
$node11->children = [
    new Node(14)
];

print_r(postorder($root2)); // Output: [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1]
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Initialization:

    • Create a stack and push the root node onto it.
    • Create an empty array result to store the final postorder traversal.
  2. Traversal:

    • Pop the node from the stack, insert its value at the beginning of the result array.
    • Push all its children onto the stack.
    • Continue until the stack is empty.
  3. Result:

    • The result array will contain the nodes in postorder after the loop finishes.

This iterative approach effectively simulates the postorder traversal by using a stack and reversing the process typically done by recursion.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more