← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
You are given the root node of an n-ary tree structure where each node can have any number of child nodes. Your task is to compute the height of this tree, which is defined as the number of nodes encountered along the longest path from the root down to the furthest leaf node.
An n-ary tree is a tree data structure where each node can have zero or more children (unlike a binary tree which has at most two children per node). The root is considered to be at depth 1, its children at depth 2, and so on.
If the tree is empty (root is null), the height should be 0.
Example 1:
Input: root = Node(1, []) Output: 1 Explanation: The tree contains only the root node, so the height is 1.
Example 2:
Input: root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)]) Output: 3 Explanation: The tree has three levels. The longest path is 1 -> 3 -> 5 (or 1 -> 3 -> 6), which contains 3 nodes.
Example 3:
Input: root = Node(1, [Node(2, [Node(3, [Node(4)])])]) Output: 4 Explanation: This is a linear chain where each node has exactly one child. The path contains 4 nodes.
Example 4:
Input: root = null Output: 0 Explanation: An empty tree has no depth.
Hint 1: Recursive Thinking Think about how the height of a tree relates to the heights of its subtrees. The height of a tree is closely related to the maximum height among all of its children's subtrees. Can you express the problem recursively?
Hint 2: Base Case What should you return when you reach a null node or a leaf node? A null node contributes 0 to the depth, while any existing node adds 1 to the depth count.
Hint 3: Alternative Approach While recursion is natural for trees, you could also solve this iteratively using a queue-based level-order traversal (BFS). Count how many levels you process.
Full Solution ` class Node: def init(self, val=0, children=None): self.val = val self.children = children if children is not None else []
def maxDepth(root): # Base case: empty tree has depth 0 if root is None: return 0
# If node has no children, it's a leaf with depth 1 if not root.children: return 1 # Recursively find the max depth among all children # Add 1 to account for the current node max_child_depth = 0 for child in root.children: max_child_depth = max(max_child_depth, maxDepth(child)) return 1 + max_child_depth`
Approach:
This solution uses a recursive depth-first search (DFS) approach:
- Base Case: If the root is null, return 0 since an empty tree has no depth.
- Leaf Case: If a node has no children, it's a leaf node and contributes a depth of 1.
- Recursive Case: For any node with children, we recursively calculate the depth of each child subtree and take the maximum. We then add 1 to account for the current node itself.
- The recursion naturally explores all paths from root to leaves and returns the maximum.
Time Complexity: O(n) where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(h) where h is the height of the tree, due to the recursion call stack. In the worst case of a completely unbalanced tree (linear chain), this could be O(n).
Alternative BFS Solution:
` from collections import deque
def maxDepth(root): if root is None: return 0
queue = deque([root]) depth = 0 # Level-order traversal while queue: depth += 1 level_size = len(queue) # Process all nodes at current level for _ in range(level_size): node = queue.popleft() # Add all children to queue for next level for child in node.children: queue.append(child) return depth`
The BFS approach processes the tree level by level, counting each level. This has the same time complexity O(n) but uses O(w) space where w is the maximum width of the tree (maximum number of nodes at any level).