# Diamond Tree

## Introduction

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.

Also see, Data Structures

## 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:

- The tree's first K levels should be a balanced binary tree, with node values starting at one and increasing from left to right.
- 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 the 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

1

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 level in the following manner. Till the queue contains at least two nodes:

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

This will automatically generate the next K - 1 level.

### Algorithm

- Create the ‘ROOT’node with value one and push it in a queue ‘TREENODES’.
- Initialize ‘REMAININGLEVELS’with K - 1.
- While REMAININGLEVELS > 0, do the following:
- Let SIZE = TREENODES.size()
- 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.

- The previous step will create K levels in the tree.
- Now, while the size of the queue is greater than one, do the following:
- Pop two nodes as FIRSTNODE and SECONDNODE from the queue.
- Create a new node NEXTNODE with value FIRSTNODE.value + SECONDENODE.value
- Make NEXTNODE the right child of the FIRSTNODE and left child of the SECONDNODE.

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

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

Cheers!