Diamond Tree

Approach

We can create the diamond-like tree structure till the Kth level in the standard way. The diamond-like tree structure is a balanced binary tree till the Kth level. So, we can create the root of the tree and push it in a queue. Now, we can build up the tree one level at a time until the number of levels is less than K. For creating a new level, we pop all the nodes in the last level and create their left and right children. We then push these newly created nodes to the queue for generating the next level.

We can create the next K - 1 level in the following manner. Till the queue contains at least two nodes:

1. Pop two nodes from the queue and let their values be ‘V1’ and ‘V2’.
2. Create a new node with the value ‘V1’ + ‘V2’.
3. Make the newly-created node the right child of the first node and the left child of the second node.
4. Push this node to the queue.

This will automatically generate the next K - 1 level.

Algorithm

1. Create the ‘ROOT’node with value one and push it in a queue ‘TREENODES’. 
2. Initialize ‘REMAININGLEVELS’with K - 1.
3. While REMAININGLEVELS > 0, do the following:
   1. Let SIZE = TREENODES.size()
   2. While SIZE is greater than zero, pop a node from the queue and create its left and right children with appropriate values. Push these children to the queue.
4. The previous step will create K levels in the tree.
5. Now, while the size of the queue is greater than one, do the following:
   1. Pop two nodes as FIRSTNODE and SECONDNODE from the queue.
   2. Create a new node NEXTNODE with value FIRSTNODE.value + SECONDENODE.value
   3. Make NEXTNODE the right child of the FIRSTNODE and left child of the SECONDNODE.
6. Print the tree using the level-order traversal of the diamond tree.

Program

#include <iostream>
#include <queue>
using namespace std;

// A node of the tree.
class Node
{
public:
    int val;
    Node *left, *right;

    // Constructor to create an object.
    Node(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};

// Function to create the diamond tree structure.
void createDiamondTree(Node *root, int level)
{

    // Number of levels to create in the balanced part.
    int remainingLevels = level - 1;

    // Queue to contain the nodes.
    queue<Node *> treeNodes;

    // Push the root to start the process.
    treeNodes.push(root);

    // Starting value of nodes.
    int val = 1;

    while (remainingLevels > 0)
    {

        // Current size of queue.
        int size = treeNodes.size();
        while (size > 0)
        {

            Node *node = treeNodes.front();

            // Pop the node.
            treeNodes.pop();

            val += 1;

            // Create the left and right children.
            Node *newnode = new Node(val);
            node->left = newnode;
            val += 1;
            newnode = new Node(val);
            node->right = newnode;

            // Set the left and right children.
            treeNodes.push(node->left);
            treeNodes.push(node->right);

            size--;
        }

        // One level is complete now.
        remainingLevels--;
    }
    while (treeNodes.size() > 1)
    {

        // Pop two nodes.
        Node *firstNode = treeNodes.front();
        treeNodes.pop();
        Node *secondNode = treeNodes.front();
        treeNodes.pop();

        // Merging step.
        // Create a new node with the sum of their values.
        Node *nextnode = new Node(firstNode->val + secondNode->val);

        // Set the right and left child of the pair of nodes to the new node.
        firstNode->right = nextnode;
        secondNode->left = nextnode;
        treeNodes.push(nextnode);
    }
}

// Level order traversal of the tree.
void printDiamondTree(Node *root, int levels)
{

    if (root == NULL)
        return;
    int remLevels = levels - 1;

    // For level order traversal.
    queue<Node *> treeNodes;

    // For the process to start.
    treeNodes.push(root);
    while (remLevels > 0)
    {

        int size = treeNodes.size();
        while (size > 0)
        {

            Node *node = treeNodes.front();
            treeNodes.pop();

            // Print the val.
            cout << node->val << " ";
            // Push the left and right children.
            treeNodes.push(node->left);
            treeNodes.push(node->right);

            size--;
        }
        remLevels--;
        cout << endl;
    }

    // While the queue is not empty.
    while (treeNodes.size() > 0)
    {

        // Get the size of current level.
        int size = treeNodes.size();

        while (size--)
        {

            Node *node = treeNodes.front();
            treeNodes.pop();

            // Print the node's value.
            cout << node->val << " ";

            if (node->right != NULL)
            {
                // For the next level.
                treeNodes.push(node->right);
            }
        }
        cout << endl;
    }
}

int main()
{

    // Enter the value of K.
    int K;
    cout << "Enter value of K: ";
    cin >> K;

    // Start with the creation of root.
    Node *root = new Node(1);

    // Create the structure.
    createDiamondTree(root, K);

    // Print the tree.
    cout << "Printing the Diamond Tree" << endl;
    printDiamondTree(root, K);
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the value of K: 4

Output

Printing the Diamond Tree

1 

2 3 

4 5 6 7 

8 9 10 11 12 13 14 15 

17 21 25 29 

38 54 

92

Complexity Analysis

Time Complexity

The time complexity of the above approach is O(N), where ‘N’ is the total number of nodes in the diamond tree. Given the value of K, can you guess the number of nodes in the diamond tree?

Yeah, you got it:  2^K - 1 + 2^(K - 1 ) - 1 = 3*2^(K -1) -2.

Thus the time complexity of the above approach is O(2^K).

Space Complexity

The space complexity of the above approach is O(2^K) as at any moment, the maximum number of nodes in the queue is 2^K.

Check out this problem - Diameter Of Binary Tree

Frequently Asked Questions

What is a Binary Tree?

A Binary Tree is a type of Tree Data Structure where each node in the tree has a maximum of two children,

What is a Balanced Binary Tree?

A Balanced Binary Tree is a type of Binary Tree in which the heights of the left and right subtree of a node differ by at maximum1.

Conclusion

This blog discussed a problem based on binary trees involving level-order tree traversal and a constructive implementation. We learned how to break down a problem into various interdependent components and solve each separately. Such techniques are especially helpful in complex and vast problems where the problem can be broken down into several interrelated components. There are various other ways of traversing binary trees like pre-order, post-order, and inorder traversals.

Recommended Reading:

• Symmetric Binary Trees
• Diameter of Binary Tree
• Expression Tree
• Palindromic Levels of a Binary Tree
• Top Trees Interview Questions

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!