Diamond Tree

Aman Chourasiya
Last Updated: May 13, 2022

Understanding

This blog will discuss a constructive problem based on binary trees. Constructive problems are well-known in coding contests and interviews. Constructive problems usually involve some tricky coding implementations applying a combination of loop constructs. In this blog, we will take up a challenge involving level order traversals in binary trees and a tricky implementation technique.

Problem Statement

Ninja has given you a number, 'K.' The goal is to design a Diamond-like Tree structure that meets the following two criteria:

  1. The tree's first K levels should be a balanced binary tree, with node values starting at one and increasing from left to right.
  2. By merging every pair of nodes with their total stored as their child, the next K – 1 levels should form a diamond-like shape.

As you can observe, if you start merging every pair of nodes from the Kth level, you will end up with one node at the 2*K - 1 level.

Input

Enter value of K: 2

Output

Printing the Diamond Tree

1

2 3

5

Explanation

The diamond-like tree structure will look like this for K = 2:

          1                            

         / \    

        2 3     

         \ /

          5

As you can see, the tree is a balanced binary tree until the second level (the root is at the first level). At the third level, the pair of nodes containing 2 and 3 are merged to create a new node with the value 5(2+3). This node is made the child of the pair of the nodes.

Input

Enter value of K: 4

Output

Printing the Diamond Tree

2 3 

4 5 6 7 

8 9 10 11 12 13 14 15 

17 21 25 29 

38 54 

92

Explanation

The diamond-like tree structure will look like this for K = 4:

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 levels 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 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 levels.

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);
}

Input

Enter value of K: 4

Output

Printing the Diamond Tree

2 3 

4 5 6 7 

8 9 10 11 12 13 14 15 

17 21 25 29 

38 54 

92

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.

Key Takeaways

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 inter-dependent components and solve each separately. Such techniques are especially helpful in complex and vast problems where the problem can be broken down into several inter-related components. There are various other ways of traversing binary trees like pre-order, post-order, inorder traversals.

Hence learning never stops, and there is a lot more to learn.

So head over to our practice platform CodeStudio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Was this article helpful ?
0 upvotes