{x}
blog image

Add One Row to Tree

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, 104].
  • The depth of the tree is in the range [1, 104].
  • -100 <= Node.val <= 100
  • -105 <= val <= 105
  • 1 <= depth <= the depth of tree + 1

Solution Explanation for Add One Row to Tree

This problem involves adding a new row of nodes with a specified value at a given depth in a binary tree. We'll explore two common approaches: Depth-First Search (DFS) and Breadth-First Search (BFS).

Approach 1: Depth-First Search (DFS)

This approach recursively traverses the tree. The base case is when a node is null. The key logic lies in checking if the current depth (d) matches the target depth minus 1 (depth - 1). If it does, we create two new nodes with the given val and attach them as the left and right children of the current node, appropriately linking them to the existing children. If the depth is not reached, we recursively call the dfs function on the left and right subtrees, incrementing the depth.

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. This is due to the recursive call stack in the worst-case scenario of a skewed tree. In a balanced tree, this becomes O(log N).

Approach 2: Breadth-First Search (BFS)

This approach uses a queue to traverse the tree level by level. We iterate through the tree until we reach the specified depth minus 1. At that depth, we modify each node to add the new row.

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node at least once.

Space Complexity: O(W), where W is the maximum width of the tree (the maximum number of nodes at any level). In a balanced tree, this would be O(N/2) ≈ O(N). In a skewed tree, it would be O(1).

Code Examples

The code examples provided demonstrate both approaches in several programming languages. Note that the BFS approach generally has better space complexity for balanced trees because it doesn't have the recursive overhead. However, the DFS approach might be slightly simpler to understand and implement for some.

Note: The provided code snippets assume a standard TreeNode definition for binary trees. You might need to adjust the definition based on your specific environment or language. For example, in some languages you might need to explicitly define the TreeNode structure.

The choice between DFS and BFS depends on the specific constraints and the expected tree structure. If memory efficiency is crucial and you anticipate a relatively balanced tree, BFS might be preferred. If code simplicity is prioritized, DFS may be a better option. Both approaches have a linear time complexity, making them efficient for this problem.