N-ary Tree

[hon9g]

Problems selected by LeetCode for the topic N-ary Tree 🌐

Click ✔️ to go to each solution. The Link to each problem🌐 is at the top of each solution.

🔗 Traversal

#	title	my solution
589	N-ary Tree Preorder Traversal	✔️
590	N-ary Tree Postorder Traversal	✔️
429	N-ary Tree Level Order Traversal	✔️

🔗 Recursion

#	title	my solution
559	Maximum Depth of N-ary Tree	✔️
431	Encode N-ary Tree to Binary Tree	✔️

🔗 Conclusion

#	title	my solution
428	Serialize and Deserialize N-ary Tree

[hon9g]

589. N-ary Tree Preorder Traversal

• 🌐problem

  Iterative Pre-order Traverse

• Time Complexity: O(N)
• Space Complexity: O(N)

  /**
  * @param {Node} root
  * @return {number[]}
  */
  const preorder = function(root) {
  const res = [], stack = [root];
  while (stack.length) {
      const curr = stack.pop();
      if (!curr) continue;
      res.push(curr.val);
      stack.push(...curr.children.reverse())
  }
  return res;
  };

  Recursive Pre-order Traverse

• Time Complexity: O(N)

• Space Complexity:

  • O(log N) in average case.
  • O(N) in worst case, that there is an unbalanced tree.

    
    /**

  • @param {Node} root
  • @return {number[]} */ const preorder = function(root) { const res = []; traverse(root); return res;

  function traverse(node) { if (!node) return; res.push(node.val); for (child of node.children) { traverse(child); }
  }
  };

[hon9g]

590. N-ary Tree Postorder Traversal

• 🌐problem

  Iteravtive Post-order Traverse

• Time Complexity: O(N)
• Space Complexity: O(N)

  /**
  * @param {Node} root
  * @return {number[]}
  */
  var postorder = function(root) {
  const res = [], stack = [root];
  while (stack.length) {
      const curr = stack.pop();
      if (!curr) continue;
      res.push(curr.val);
      stack.push(...curr.children);
  }
  return res.reverse();
  };

  Recursive Post-order Traverse

• Time Complexity: O(N)

• Space Complexity:

  • O(log N) in average case.
  • O(N) in worst case, that there is an unbalanced tree.

    
    /**

  • @param {Node} root
  • @return {number[]} */ var postorder = function(root) { const res = []; traverse(root); return res;

  function traverse(node) { if (!node) return; for(child of node.children) { traverse(child); } res.push(node.val); } };

[hon9g]

429. N-ary Tree Level Order Traversal

• 🌐problem

  Iterative Level-order Traverse

• Time Complexity: O(N^2) consider .shift() takes linear
• Space Complexity: O(N)

  /**
  * @param {Node} root
  * @return {number[][]}
  */
  var levelOrder = function(root) {
  const res = [], queue = [];
  let depth = 0, num = 0;
  if (root) queue.push(root);
  while (queue.length) {
      res.push([]);
      num = queue.length;
      for (let i = 0; i < num; i++) {
          const curr = queue.shift();
          if (!curr) continue;
          res[depth].push(curr.val);
          queue.push(...curr.children);
      }
      depth++;
  }
  return res;
  };

  Recursive Level-order Traverse

• Time Complexity:
  • O(N)

• Space Complexity:

  • O(log N) in average case.
  • O(N) in worst case, that there is an unbalanced tree.

    
    /**

  • @param {Node} root
  • @return {number[][]} */ var levelOrder = function(root) { const res = []; BFS(root, 0); return res;

  function BFS(node, depth) { if (!node) return; if (depth === res.length) { res.push([]); } res[depth].push(node.val); for (child of node.children) { BFS(child, depth + 1); } } };

[hon9g]

559. Maximum Depth of N-ary Tree

• 🌐problem

  Bottom Top

• Time Complexity: O(N)
• Space Complexity: O(N)

  /**
  * @param {Node} root
  * @return {number}
  */
  var maxDepth = function(root) {
  if (!root) return 0;
  const heights = [];
  for (child of root.children) {
      heights.push(maxDepth(child));
  }
  return 1 + heights.reduce((a, b) => a < b ? b : a, 0);
  };

  Top Bottom

• Time Complexity: O(N)

• Space Complexity: O(H)

  /**
  * @param {Node} root
  * @return {number}
  */
  var maxDepth = function(root) {
  let n = 0;
  DFS(root, 1);
  return n;
  
  function DFS(node, depth) {
      if (!node) return;
      for (child of node.children) {
          DFS(child, depth + 1);
      }
      if (n < depth) {
          n = depth;
      }
  }
  };

[hon9g]

431. Encode N-ary Tree to Binary Tree

• 🌐problem

• Time Complexity: O(N^2)
• Space Complexity: O(N)

  class Codec {
  constructor() {
  }
  /** 
   * @param {Node} root
   * @return {TreeNode}
   */
  // Encodes an n-ary tree to a binary tree.
  encode = function(root) {
      if (!root) return null;
      const rootNode = new TreeNode(root.val);
      const queue = [[rootNode, root]];
      while (queue.length) {
          const [parent, curr] = queue.shift();
          let prevBNode = null, headBNode = null;
          for (child of curr.children) {
              const newBNode = new TreeNode(child.val);
              if (prevBNode) {
                  prevBNode.right = newBNode;
              } else {
                  headBNode = newBNode;
              }
              prevBNode = newBNode;
              queue.push([newBNode, child]);
          }
          parent.left = headBNode;
      }
      return rootNode;
  };
  /** 
   * @param {TreeNode} root 
   * @return {Node}
   */
  // Decodes your binary tree to an n-ary tree.
  decode = function(root) {
      if (!root) return null;
      const rootNode = new Node(root.val, []);
      const queue = [[rootNode, root]];
      while (queue.length) {
          const [parent, curr] = queue.shift();
          let firstChild = curr.left;
          let sibling = firstChild;
          while (sibling) {
              const newNode = new Node(sibling.val, []);
              parent.children.push(newNode);
              queue.push([newNode, sibling]);
              sibling = sibling.right;
          }
      }
      return rootNode;
  };
  }

[hon9g]

428. Serialize and Deserialize N-ary Tree

• 🌐problem

  complexity analysis

• Time Complexity:
• Space Complexity: