Leetcode 623: Add One Row to Tree [Solution]

This question consists of simple problem with multiple ways to solve this. I like recursion so I decided to go with that approach. The question doesn't seem to have many edge cases so if you are getting correct answer for the example test cases and a little variation to them, you will get your submission approved easily.

Difficulty: Medium
Jump To:

• Problem Statement
• Explanation
• Solution
• Implementation

---

Problem Statement

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5   

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

1. The given d is in the range [1, maximum depth of the given tree + 1].
2. The given binary tree has at least one tree node.

---

Explanation

So the problem is quite simple, You are given a non-empty binary tree and a value v which needs to be inserted as a child at depth d for all non-empty parent nodes. The new node will be at both left and right edge of the parent. The child nodes/subtree of the parent need to be set as the child of the newly created node with the same direction left/right. This should be clear with the given examples.

---

Solution

We are going to do only the below things:

1. If depth=1 i.e. we need to add the value at root, then we just need to create a new node with value v and make the current root its left child and return the pointer to the new node.
2. We need to traverse the tree in both directions (left/right) till we reach the depth d-1. Let's say we are at the node parent, this is the node below which the new nodes need to be added.
3. Now we need to create a new node for the left subtree of parent so this new node's left pointer will point to the left subtree of parent and then we'll make parent's left pointer point to the new node. That's how we have added a node between the parent and left subtree.
4. Same needs to be done for the right subtree.

As we'll be going down to the tree, we can call it DFS(Depth First Search) based on recursion. So Time Complexity: of this solution may go to O(n) as we might need to add the nodes below the leaf. As recursion uses stack so the Space Complexity: can be O(n) in the worst case.

---

Implementation

C++ Code:

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        // If need to add the row on root
        if(d==1){
            // Just create a new node with value v 
            // and current root as left child
            TreeNode *ptr = new TreeNode(v, root, nullptr);
            return ptr;
        }

        // Traverse down to the parent node at depth d-1
        // to add row at depth d(>1)
        addRow(root, v, d-1);

        // Return same pointer root with modified tree
        return root;
    }

    // Function to traverse down to the depth d-1 and add row
    void addRow(TreeNode* parent, int v, int dep){
        // If node is NULL the do nothing
        if(!parent)
            return;

        // If we have reached depth d-1 i.e. dep=1
        if(dep==1){
            TreeNode *temp;

            // Store left ptr
            temp = parent->left; 
            // Replace left ptr with new node with value v
            parent->left = new TreeNode(v);
            // Set stored left pointer as new node's left ptr
            parent->left->left = temp;

            // Store right ptr
            temp = parent->right;
            // Replace right ptr with new node with value v
            parent->right = new TreeNode(v);
            // Set stored right pointer as new node's right ptr
            parent->right->right = temp;
        }
        // Else go deeper
        else{
            addRow(parent->left, v, dep-1);
            addRow(parent->right, v, dep-1);
        }
    }
};

Runnable C++ Code:

Comments

[anigah]

درج اگهی و تبلیغات در سایت‌ها برای کسب و کارها و افرادی که خدمات یا محصولات خود را به دیگران عرضه می‌کنند، بسیار مفید و موثر است. در زیر به برخی از فواید این کار اشاره می‌کنم: دسترسی به مخاطبین هدف: سایت‌ها بستری مناسب برای دسترسی به مخاطبین هدف شما فراهم می‌کنند. با درج اگهی‌ها در سایت‌های مرتبط با حوزه کسب و کار یا محصول خود، اطلاعات شما به طرح هدفمند و دقیق‌تری دست می‌یابد.افزایش آگاهی از برند: با تبلیغات مکرر و هدفمند، برند شما در ذهن مخاطبان تثبیت می‌شود و آگاهی‌های بیشتری از وجود کسب و کار یا محصول شما ایجاد می‌شود.افزایش ترافیک و بازدیدکنندگان: اگهی‌ها و تبلیغات شما ممکن است باعث افزایش ترافیک تبلیغات رایگان و بازدیدهای سایت شما شود، که این موضوع بهبود رتبه سایت شما در موتورهای جستجوی اینترنتی را نیز تسهیل می‌کند.افزایش فروش و درآمد: اگهی‌ها و تبلیغات موثر، افزایش فروش و درآمد را ایجاد می‌کنند. اگاهی مخاطبان از محصولات یا خدمات شما، احتمال تبدیل آن‌ها به مشتریان وفادار را بالا می‌برد.انعطاف‌پذیری و کنترل: با درج اگهی‌ها و تبلیغات در سایت‌ها، شما کنترل کاملی بر روی محتوا و زمان نمایش آگهی‌ها خواهید داشت. همچنین، می‌توانید استراتژی‌های مختلف را برای بهینه‌سازی تبلیغات خود اجرا کنید.هزینه‌های کمتر: معمولاً درج اگهی و تبلیغات در سایت‌ها هزینه‌های کمتری نسبت به روش‌های تبلیغاتی سنتی دارد و می‌تواند به صرفه‌ترین راه برای ارتقاء کسب و کار باشد.اندازه‌گیری دقیق و تحلیل‌پذیری: در تبلیغات اینترنتی، شما می‌توانید نتایج تبلیغات خود را با استفاده از ابزارهای تحلیل وب اندازه‌گیری کنید و عملکرد تبلیغات خود را تحلیل کنید. این اطلاعات به شما کمک می‌کند تا استراتژی‌های بهتری ایجاد کنید و روند بهبود کسب و کار خود را مشاهده کنید.به طور کلی، استفاده از اگهی و تبلیغات در سایت‌ها از طریق روش‌هایی مانند بنرها، تبلیغات پاپ‌آپ، محتوای مرتبط و ... می‌تواند برای افزایش شناخته‌شدگی، رشد کسب و کار و افزایش فروش بسیار موثر باشد.