623. Add One Row to Tree

Problem Description

The goal of this problem is to add a new row to a binary tree, with all new nodes having the same value. The new row should be added at a specified depth in the tree, where the root node starts at depth 1. Here's how the process should work:

• If depth equals 1, a new root node with the given val should be created, and the entire original tree becomes the left subtree of this new root.
• For depths greater than 1, we look for all nodes at depth - 1. For each of these nodes, we create two new children with the given val.
  • The new left child becomes the parent of the original left subtree of the node.
  • The new right child becomes the parent of the original right subtree of the node.
• This process effectively inserts a row of new nodes at the specified depth, pushing the existing nodes at that depth (if any) to become children of the newly added nodes.

Intuition

The intuition behind the solution is to traverse the tree and locate the nodes at depth - 1. For each of these nodes, we then attach new children nodes with the given val. The essential steps we follow are:

• If depth is 1, we don't need to traverse the tree, because we simply create a new root with the given val and link the entire tree as the left subtree of this new root node.
• If depth is greater than 1, we use depth-first traversal (DFS) to reach the nodes at depth - 1.
  • During the traversal, we keep track of the current depth.
  • Once we reach the required level (depth - 1), we perform the insertion of new nodes.
    • This involves creating two new tree nodes with val as their value.
    • The new left node takes the current node's left subtree, and the new right node takes the current node's right subtree.
• After performing the insertions at the required depth, we ensure the rest of the tree remains unchanged by only applying changes where necessary.

In this approach, we modify the tree in place without creating a separate structure, and we only create new nodes where the row is supposed to be added.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The provided solution utilizes recursion for a depth-first search approach to solve the problem efficiently. Here's a step-by-step explanation of how the algorithm operates:

1. The dfs function defined within the Solution class recursively explores the binary tree.
2. The dfs function takes two parameters: root which represents the current node in the binary tree and d which indicates the current depth of the recursive call.
3. The base case checks if root is None, in which case the function simply returns without performing any action, as we've reached a leaf node's child.
4. If the current depth d is equal to depth - 1, it means we've reached the level above where the new row should be inserted. We perform the following insertions in this case:
   • Create a new TreeNode with a value of val and set its left child to the current node's original left subtree (root.left). The new node is then assigned to root.left.
   • Similarly, create another new TreeNode with a value of val for the right side and assign the current node's original right subtree (root.right) to the new node's right child. This new node is then assigned to root.right.
5. If the current depth d is not yet at depth - 1, the function makes recursive calls to continue the search down the left and right subtrees, respectively, incrementing the depth d by 1.
6. The main part of the addOneRow method checks if depth equals 1. If so, a new TreeNode is created with the specified val and the entire original tree as its left subtree. This new node becomes the new root.
7. If depth is greater than 1, the recursive dfs call is initiated with root and a starting depth of 1.
8. After the recursive calls complete, the original root of the tree is returned with the modifications in place (unless a new root was created, in which case that is returned).

The algorithm effectively leverages the call stack as its primary data structure, storing the state of each node's exploration during the recursion. The overall time complexity of this solution is O(n), where n is the number of nodes in the tree, since in the worst case, every node is visited once.

Example Walkthrough

To illustrate the solution approach, let's consider a binary tree and the task of adding a row of nodes with value v at a given depth k.

Assume we have the following binary tree:

1     4
2   /   \
3  2     6
4 / \   / \
53   1 5   7

And we want to add a row of nodes with value 5 at depth 3.

Starting with addOneRow, we check if the depth is 1. It's not, since we want to add the row at depth 3. Therefore, we proceed to call the dfs function passing the root of the tree and the initial depth 1.

The dfs function begins to traverse the tree. At the initial depth, none of the conditions to insert a node are met, so the function recursively calls itself for the left child 2 and right child 6 of the root 4, with depth 2.

For both child nodes, 2 and 6, we are still not at the target depth (depth - 1 which is 2) for insertion, so the function recursively calls itself for their children, with depth incremented to 3, which is our target for insertion.

Node 2 has children 3 and 1, and node 6 has children 5 and 7. Now that d equals depth - 1 at this level, we perform the insertions:

• The original left child of node 2 (which is 3) becomes the left child of a new node with val 5, and this new node is then assigned as the new left child of node 2.
• Similarly, the original right child of node 2 (which is 1) becomes the left child of another new node with val 5, which is then assigned as the new right child of node 2.

The same process occurs for node 6 and its children.

With insertions complete, the function returns to its caller at the higher level and ultimately back to addOneRow, which returns the original root of the binary tree.

After the row addition, the modified binary tree looks like this:

1     4
2   /   \
3  2     6
4 / \   / \
55   5 5   5
6/     /     \
73     1      7
8       \
9        5

In this example, only the nodes that needed new children were changed—2 and 6—and no other part of the tree was modified unnecessarily.

Solution Implementation

Time and Space Complexity

The provided code defines a solution to add a row of nodes with a specific value at a given depth in a binary tree. To analyze the time and space complexity, let's consider n to be the total number of nodes in the binary tree.

Time Complexity:

The time complexity of the code can be determined by the number of nodes the algorithm visits. The function dfs is a recursive function that visits each node exactly once when the depth is equal to or greater than the depth of insertion (d >= depth).

In the worst-case scenario, which occurs when the new row is added at the maximum depth of the tree, the algorithm must visit all n nodes to determine their depth and to potentially add the new nodes.

Therefore, the time complexity of the code is O(n).

Space Complexity:

Space complexity comes from the recursive stack space used in the depth-first search (DFS). In the worst-case scenario, the depth of the recursive call stack is proportional to the height of the tree.

• In the case of a balanced binary tree, the height of the tree is logarithmic, and the space complexity would be O(log n).
• For a skewed binary tree (a tree in which every node has only one child), the height could be as high as n, and the worst-case space complexity would be O(n).

Therefore, the overall space complexity is O(h) where h is the height of the tree, which ranges from O(log n) for a balanced tree to O(n) for a skewed tree.

Learn more about how to find time and space complexity quickly using problem constraints.