# C++, Java and Python Solutions (DFS via Recursion)

• Intuition
It doesn't really matter how you traverse the tree, so long as you keep track of your current depth and hit all left children before their right siblings.

Then, you can simply construct the returned list in place, by adding values directly to the sublist for your current level.

C++ (DFS via Recursion)

``````class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
levelOrderImpl(root, ret, 0);
return ret;
}
private:
void levelOrderImpl(TreeNode* root, vector<vector<int>>& ret, int level) {
if (!root) return;
if (level >= ret.size()) {
ret.push_back({});
}
ret.at(level).push_back(root->val);
levelOrderImpl(root->left, ret, level+1);
levelOrderImpl(root->right, ret, level+1);
}
};
``````

Java (DFS via Recursion)

``````class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return Collections.emptyList();
List<List<Integer>> ret = new ArrayList<>();
levelOrderImpl(root, ret, 0);
return ret;
}

private void levelOrderImpl(TreeNode root, List<List<Integer>> ret, int level) {
if (root == null) return;
if (level >= ret.size()) {
}
levelOrderImpl(root.left, ret, level+1);
levelOrderImpl(root.right, ret, level+1);
}
}
``````

Python (DFS via Recursion)

``````class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root: return []
ret = [[]]
self.levelOrderImpl(root, ret, 0)
return ret

def levelOrderImpl(self, root, ret, level):
"""
:type root: TreeNode
:type ret: List[List[int]]
:type level: integer
:rtype: None
"""
if not root: return
if len(ret) < level+1:
ret.append([root.val])
else:
ret[level].append(root.val)
self.levelOrderImpl(root.left, ret, level+1)
self.levelOrderImpl(root.right, ret, level+1)
``````

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the tree. This should be clear from the fact that each node is examined exactly once.
• Space Complexity:
• If BFS, O(w), where w is the maximum width of the tree, in the queue
• If DFS, O(d), where d is the maximum depth of the tree, either in the recursion stack or your own stack.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.