"""Leetcode 559. Maximum Depth of N-ary Tree
Easy

URL: https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node
down to the farthest leaf node.

For example, given a 3-ary tree:
      1
    / | \
   3  2  4
  / \
 5   6
We should return its max depth, which is 3.

Note:
- The depth of the tree is at most 1000.
- The total number of nodes is at most 5000.
"""

# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        """
        :type val: int
        :type children: list
        :rtype: int
        """
        self.val = val
        self.children = children


class SolutionDFSRecur(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int

        Time complexity: O(n).
        Space complexity: O(h), where h is the height of tree.
        """
        # Apply recursive DFS in preorder traversal fashion.
        if not root:
            return 0

        # Update child_depth for all children nodes.
        child_depth = 0
        for child in root.children:
            child_depth = max(child_depth, self.maxDepth(child))

        # Return single node depth (1) + child depth.
        return 1 + child_depth


def main():
    # Output: 3
    root = Node(1, [])
    root.children.append(Node(3, []))
    root.children.append(Node(2, []))
    root.children.append(Node(4, []))
    root.children[0].children.append(Node(5, []))
    root.children[0].children.append(Node(6, []))
    print SolutionDFSRecur().maxDepth(root)


if __name__ == '__main__':
    main()

@@ -937,18 +937,41 @@
  of tree
+; O(n) for single sided
 .%0A
-
         
@@ -1344,16 +1344,768 @@
 depth%0A%0A%0A
+class SolutionBFS(object):%0A    def maxDepth(self, root):%0A        %22%22%22%0A        :type root: Node%0A        :rtype: int%0A%0A        Time complexity: O(n).%0A        Space complexity: O(m), where m is the number of nodes on the bottom.%0A        %22%22%22%0A        # Apply (iterative) BFS to visit level in preorder traversal fashion.%0A        if not root:%0A            return 0%0A%0A        depth = 0%0A        queue = %5Broot%5D%0A%0A        while queue:%0A            # Increment depth due to there is node in this level.%0A            depth += 1%0A%0A            # Visit all nodes in the same level.%0A            for i in range(len(queue)):%0A                current = queue.pop()%0A%0A                for child in current.children:%0A                    queue.insert(0, child)%0A%0A        return depth%0A%0A%0A
 def main
@@ -2307,24 +2307,24 @@
 ode(5, %5B%5D))%0A
-
     root.chi
@@ -2356,24 +2356,69 @@
 Node(6, %5B%5D))
+%0A%0A    print SolutionDFSRecur().maxDepth(root)
 %0A    print S

Complete bfs sol