DAA: Continuous Tree
Continuous Tree
A continuous tree is the one in which the nodes from root to leaf path, the two adjacent node values, have a difference of 1.
Input : 3
/ \
2 4
/ \ \
1 3 5
Output: "Yes"
3->2->1 every two adjacent node's absolute difference is 1
3->2->3 every two adjacent node's absolute difference is 1
3->4->5 every two adjacent node's absolute difference is 1
Input: 7
/ \
5 8
/ \ \
6 4 10
Output: "No"
For solving this problem, the various corner cases are to be kept in mind.
- Empty tree
- Single node tree
- Node with only one left child
- Node with only one right child
Approach 1:
Recursively calculates if the left is right subtrees are continuous. During this check, we also see that if the difference between the current node key and the child key is one.
C++ code:
#include <bits/stdc++.h>
using namespace std;
// Binary tree Node structure
struct Node {
int data; // the value of node
struct Node *left, *right; // the left and right pointer to a node
};
// Allocate new memory to a node
struct Node* newNode(int data)
{
struct Node* node = new Node; // create a new node
node->data = data; // insert node value
node->left = node->right = NULL; // the left and right pointers are currently NULL
return (node); // return current node
}
// The function return true if contious tree exist else false
bool treeContinuous(struct Node* ptr)
{
// if next node do not exist
if (ptr == NULL) // return true
return true;
// when left and right are NULL it means current node is leaf node so return true
if (ptr->left == NULL && ptr->right == NULL)
return true;
// the case where left subtree come empty
if (ptr->left == NULL)
return (abs(ptr->data - ptr->right->data) == 1) && treeContinuous(ptr->right);
// the case where right subtree is empty
if (ptr->right == NULL)
return (abs(ptr->data - ptr->left->data) == 1) && treeContinuous(ptr->left);
// the case where none of them is empty
return abs(ptr->data - ptr->left->data) == 1 && abs(ptr->data - ptr->right->data) == 1 && treeContinuous(ptr->left) && treeContinuous(ptr->right); // call recursively for left and right
}
// Main function
int main()
{
struct Node* root = newNode(3); // create root node
root->left = newNode(2); // left child of root
root->right = newNode(4); // right child of root
root->left->left = newNode(1); // left child of parent left
root->left->right = newNode(3); // right child of parent left
root->right->right = newNode(5); // child of parent right
treeContinuous(root) ? cout << "Yes" : cout << "No"; // call function to check contious
return 0;
}
Output:
Yes
Approach 2:
We use a queue data structure in this approach and use BFS traversal. While traversing level by level we check if the difference between parent and child is one and the same is true for all the nodes until leaf node the tree is continuous.
C++ code:
#include <bits/stdc++.h>
using namespace std;
// create a binary tree node structure
struct node {
int val; // node value
node* left; // left pointer to node
node* right; // right pointer to node
node() // constructor
: val(0) // initally node valye is zero
,
left(nullptr) // left pointer is null
,
right(nullptr) // right pointer is null
{
}
node(int x) // parameterised constructor
: val(x) // x value of a node
,
left(nullptr) // left pointer is null
,
right(nullptr) // right pointer is null
{
}
node(int x, node* left, node* right) // constructor with left and right pointer
: val(x) // x value of a node
,
left(left) // left pointer point to passed left
,
right(right) // right pointer pointing to passed right
{
}
};
// // The function return true if contious tree exist else false
bool continuous(struct node* root)
{
// empty tree is not continuous return false
if (root == NULL)
return false;
int flag = 1; // boolean flag
queue<struct node*> Q; // queue data structure
Q.push(root); // push root to queue
node* temp; // create temp node
// ITERATE UNITL QUEUE IS EMPTY
while (!Q.empty()) {
temp = Q.front(); // Take current node
Q.pop(); // pop it from queue
// if left child exist
if (temp->left) {
// check if difference between temp value and value of temp left is 1
if (abs(temp->left->val - temp->val) == 1)
Q.push(temp->left); // push left to temp
else {
flag = 0; // else flag become zero
break;
}
}
// if right child exists
if (temp->right) {
// check if difference between temp value and value of temp right is 1
if (abs(temp->right->val - temp->val) == 1)
Q.push(temp->right); // push right to temp
else {
flag = 0; // else flag become zero
break;
}
}
}
if (flag) // check flag
return true;
else
return false;
}
// Main function
int main()
{
struct node* root = new node(3); // create root node with value 3
root->left = new node(2); // left child of root
root->right = new node(4); // right child of root
root->left->left = new node(1); // left child of parent left
root->left->right = new node(3); // right child of parent right
root->right->right = new node(5); // right child of right node
// check if continous tree
if (continuous(root))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Output:
Yes
Time complexity: O(n)