Python 0623.py
class Solution:
def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
if not root:
return None
if depth == 1:
return TreeNode(val, root, None)
if depth > 2:
self.addOneRow(root.left, val, depth - 1)
self.addOneRow(root.right, val, depth - 1)
return root
root.left = TreeNode(val, root.left, None)
root.right = TreeNode(val, None, root.right)
return root
Difficulty
and has an acceptance rate of about 64% (400k+ submissions).
Typical patterns to solve this problem:
- Binary Tree
- Breadth First Search
- Depth First Search
- Tree
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a method addOneRow that inserts a new row of nodes with a given value into a binary tree at a specified depth. The function works recursively, descending the tree until it reaches the level just above the target depth, then creates new TreeNode instances that become the parents of the original sub-trees at that level. The method returns the possibly modified root of the tree.
Core Logic
The entry point checks for an empty tree and handles the special case where the new row must become the new root.
if not root:
return None
if depth == 1:
return TreeNode(val, root, None)
When the desired depth is deeper than the immediate children of the current node, the function recurses on both left and right sub-trees, decreasing the depth counter by one on each call.
if depth > 2:
self.addOneRow(root.left, val, depth - 1)
self.addOneRow(root.right, val, depth - 1)
return root
When the recursion reaches the node whose children are at the target depth (i.e., depth == 2), new nodes are inserted. The original left child becomes the left child of the newly created node, and the original right child becomes the right child of another newly created node.
root.left = TreeNode(val, root.left, None)
root.right = TreeNode(val, None, root.right)
return root
The method ultimately returns the original root unless the insertion occurs at depth 1, in which case a new root is created.
Edge Cases
The code explicitly handles three edge conditions:
- An empty input tree results in a
Nonereturn, avoiding any further processing. - A request to add a row at depth 1 creates a new root node whose left child points to the original tree, preserving the entire existing structure beneath the new root.
- When the target depth is exactly one level deeper than the current node (
depth == 2), the insertion logic replaces the current node’s children with newly created nodes while keeping the original sub-trees attached to those new nodes. This ensures that no existing nodes are lost and that the tree remains properly linked.
Performance Considerations
The recursive design traverses only the branches that lead to the target depth. By stopping recursion once depth reaches 2, the algorithm avoids unnecessary descent into deeper levels of the tree. This selective traversal reduces the number of function calls and node visits compared to a naïve full-tree walk, especially when the target depth is shallow relative to the height of the tree. The in-place modification of child pointers (root.left = …, root.right = …) eliminates the need for auxiliary data structures, keeping memory usage minimal. The early return after handling the base cases (depth == 1 and depth == 2) further prevents extra work once the insertion point is reached.
ELI5 - Simplified Explanation
Think of this code like a gardener deciding where to plant new flowers in a tall tree. The tree has different levels, like branches going further away from the ground.
When the gardener looks at the tree, the first thing checked is if the tree is missing entirely. If there is no tree, there is nowhere to plant anything.
If the request is to add a new row at the very top, the gardener creates a new piece to sit at the highest point and pushes the old tree down to be underneath it.
If the gardener needs to go deeper to find the right spot, the instructions say to travel down to the left branch and the right branch, counting down the steps until reaching the row just above where the new flowers belong.
Once the gardener reaches that special row right above the spot, it is time to do the planting. A new piece is attached to the left side, and the old left branch is tucked underneath it. Then, a new piece is attached to the right side, and the old right branch is tucked underneath that one. Now the tree has a brand new row of flowers nestled right where they were asked to be.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||
| WalkCCC | C++ | Java | |||||||||
| leetcode.ca | C++ | Python | Java | Go | TS | ||||||
| LeetcodeHelp | C++ | Python | Java | ||||||||
| Progiez | C++ | Python | Java | ||||||||
| github | black-shadows | C++ | |||||||||
| charles-wangkai | Java | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fpdjsns | C++ | ||||||||||
| halfrost | Go | ||||||||||
| haoel | Python | ||||||||||
| JoshCrozier | JS | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| vthwang | Java | ||||||||||
| yuanliu666 | Kotlin | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Java | ||||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fpdjsns | C++ | ||||||||||
| halfrost | Go | ||||||||||
| haoel | Python | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| vthwang | Java | ||||||||||
| yuanliu666 | Kotlin | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ |
Videos
Solved On The Same Day
- problem 292: Nim Game
- problem 572: Subtree of Another Tree
- problem 617: Merge Two Binary Trees
- problem 671: Second Minimum Node In a Binary Tree
- problem 152: Maximum Product Subarray
- problem 207: Course Schedule
- problem 210: Course Schedule II
- problem 211: Design Add and Search Words Data Structure
- problem 213: House Robber II
- problem 237: Delete Node in a Linked List
- problem 260: Single Number III
- problem 416: Partition Equal Subset Sum
- problem 437: Path Sum III
- problem 450: Delete Node in a BST
- problem 560: Subarray Sum Equals K
- problem 606: Construct String from Binary Tree
- problem 652: Find Duplicate Subtrees
- problem 654: Maximum Binary Tree
- problem 655: Print Binary Tree
- problem 662: Maximum Width of Binary Tree
- problem 669: Trim a Binary Search Tree
- problem 687: Longest Univalue Path
- problem 1115: Print FooBar Alternately
- problem 1116: Print Zero Even Odd
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality