Is Add One Row to Tree easy or hard?

Add One Row to Tree is considered a Medium difficulty problem on LeetCode. The main challenge is correctly handling tree traversal and pointer reassignment when inserting the new nodes while preserving the existing subtrees.

Add One Row to Tree Python/Java solution

Python implementations often use recursive DFS to track depth and insert nodes when depth == d-1. Java solutions commonly use a queue for BFS level-order traversal to reach the correct level and modify children. Both implementations run in O(n) time.

How to solve Add One Row to Tree in O(n)?

Traverse the tree until reaching depth d-1 using either DFS or BFS. For each node at that level, create two new nodes with value val and attach the original left and right subtrees beneath them. Each node is processed at most once, resulting in O(n) time complexity.

What is the best approach for Add One Row to Tree?

The Breadth-First Search (level order traversal) approach is typically the most straightforward. You traverse the tree level by level using a queue until reaching depth d-1, then insert new nodes under each node at that level. This approach runs in O(n) time and uses O(w) space where w is the maximum width of the tree.

Is Add One Row to Tree asked at Google/Amazon/Meta?

Binary tree modification problems like Add One Row to Tree frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants often test traversal techniques, tree restructuring, and understanding of DFS or BFS patterns.

What data structure is used in Add One Row to Tree?

The primary data structure is a binary tree. Solutions typically use recursion with a call stack for Depth-First Search or a queue for Breadth-First Search to traverse levels and insert the new nodes at the correct depth.

What is the time complexity of Add One Row to Tree?

The time complexity is O(n) because every node in the binary tree may need to be visited once to reach the target depth. Both DFS and BFS implementations achieve this complexity. Space complexity is O(h) for recursive DFS (tree height) or O(w) for BFS (maximum level width).

Description Solution Video 15:08

623. Add One Row to Tree

Medium64.1% acceptance3 companies

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
cur's original left subtree should be the left subtree of the new left subtree root.
cur's original right subtree should be the right subtree of the new right subtree root.
If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

Example 2:

Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
The depth of the tree is in the range [1, 10⁴].
-100 <= Node.val <= 100
-10⁵ <= val <= 10⁵
1 <= depth <= the depth of tree + 1

Asked at 3 companies

Gilt Groupe

Google Bloomberg

Topics

15:08

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[4,2,6,3,1,5]
1
2

Input

[4,2,null,3,1]
1
3

Your code is saved on this device.Solution