Problem 623

Abstract / Summary

Add a new value as a new row between the root and its children in a binary tree.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
16 lines | 525 bytes | submitted September 4, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

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
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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 None return, 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.22 | σ = 1.47

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
35 links | 23 authors | 10 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

25 solutions   September 4, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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