algoadvance

Leetcode 623. Add One Row to Tree

Problem Statement

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. The root node is considered to have depth 1.

The adding rule is:

• Given the depth depth, for each not null tree node N at the depth depth - 1, create two tree nodes with value val as N’s left subtree root and N’s right subtree root.
• N’s original left subtree should be the left subtree of the new left subtree root.
• N’s original right subtree should be the right subtree of the new right subtree root.

Return the modified tree’s root.

Example:

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

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

Clarifying Questions

1. What should we do if the given depth is 1?
   • If depth is 1, then we need to add the new row at the root. This means creating a new root with the given val and making the existing tree its left subtree.
2. What kind of input validations should we consider?
   • We assume that the input binary tree is well-formed. There are no constraints on the size of the tree or the values of the nodes.

Strategy

1. Depth handling: Special case handling for depth == 1 where we need to replace the root.
2. Breadth-First Search (BFS) or Depth-First Search (DFS) at each (depth-1) to insert the new nodes.

Code

Here’s the Java code to implement the solution:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        insert(root, val, depth, 1);
        return root;
    }

    private void insert(TreeNode node, int val, int depth, int currentDepth) {
        if (node == null) {
            return;
        }
        if (currentDepth == depth - 1) {
            TreeNode tempLeft = node.left;
            TreeNode tempRight = node.right;
            node.left = new TreeNode(val, tempLeft, null);
            node.right = new TreeNode(val, null, tempRight);
        } else {
            insert(node.left, val, depth, currentDepth + 1);
            insert(node.right, val, depth, currentDepth + 1);
        }
    }
}

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the tree. This is because we need to potentially visit each node once to insert the new row at the correct depth.

Summary

1. If depth == 1, make a new root.
2. Use DFS or BFS to find the correct nodes at depth - 1.
3. Add the new nodes with value val.
4. Ensure the original subtrees are correctly assigned.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?