Algorithm for determining whether or not a tree is continuous
Return 1 if the root is NULL.
Return 1 If it's a leaf node because a leaf node is reached, which is an indication that the tree has been continuous.
If the left subtree is empty, make sure the current node is continuous to the right child (compute the absolute difference in weights) and repeat for the right subtree recursively.
If the right subtree is empty, check the current node's continuity with the left child (compute the absolute difference in weights) and proceed for the left subtree recursively.
Otherwise, calculate the absolute difference using the weights of the left and right children and proceed for the left and right subtrees recursively.
Code Implementation
// C++ program for determining whether or not a tree is continuous
#include<bits/stdc++.h>
using namespace std;
struct Node_S
{
int data;
struct Node_S* left, * right;
};
struct Node_S* newNode_S(int data)
{
struct Node_S* node = new Node_S;
node->data = data;
node->left = node->right = NULL;
return(node);
}
// Function to check continuity of tree
bool tree_Continuous(struct Node_S *ptr)
{
if (ptr == NULL)
return true;
if (ptr->left == NULL && ptr->right == NULL)
return true;
if (ptr->left == NULL)
return (abs(ptr->data - ptr->right->data) == 1) && tree_Continuous(ptr->right);
if (ptr->right == NULL)
return (abs(ptr->data - ptr->left->data) == 1) && tree_Continuous(ptr->left);
return abs(ptr->data - ptr->left->data)==1 &&
abs(ptr->data - ptr->right->data)==1 &&
tree_Continuous(ptr->left) &&
tree_Continuous(ptr->right);
}
int main()
{
struct Node_S *root = newNode_S(8);
root->left = newNode_S(7);
root->right = newNode_S(9);
root->left->left = newNode_S(8);
root->left->right = newNode_S(6);
root->left->right->left = newNode_S(5);
root->left->right->right = newNode_S(7);
tree_Continuous(root)? cout <<"✔️Continuous Tree" : cout <<"❌ Continuous Tree";
return 0;
}
Input
8
/ \
7 9
/ \
8 6
/ \
5 7
Output
✔️Continuous Tree
Time complexity
O(N) because each node is traversed only once Or, to put it another way, the amount of work you put in for each node remains constant (does not depend on the rest of the nodes).An alternative method for determining whether or not a tree is continuous - is using BFS(Queue)
The absolute difference between the parent node and all of its direct children nodes is always 1. A Continuous Tree is defined as a tree with any path from root node to leaf node having value or weight of nodes such that the absolute difference between the parent node and all of its direct children nodes is always 1.
How are contiguous storage trees implemented?
How are contiguous storage trees implemented?
The number of nodes formed can be regulated or limited using a contiguous allocation approach. This means that on a 32k system, the tree will not occupy all of the memory and will leave holes. A contiguous system speeds up the allocation process. You're aware of the location of the blocks.
What is a full binary tree, exactly?
A complete Binary tree is a form of binary tree in which each parent/internal node has two or no children. A proper binary tree is another name for it.
What is the method for storing trees in memory?
It's usually saved as an adjacency list. For each node, this is essentially a linked list. As a result, a node u's linked list contains every node v such that (u,v) is a valid tree edge. An adjacency matrix can also be used to store it.
What exactly is a null tree?
A tree with no nodes is called an empty (Null)-tree. A single-node tree is known as a root-tree. A binary tree is one where each node has no more than two offspring (parent, left, and right) A two tree is a binary tree that is either empty or has two offspring for each non-leaf.
Conclusion
This article extensively discussed Continuous Tree. We started with a brief introduction of Continuous Tree with an example and diagram, and then we learnt about Algorithm and Code Implementation.
After reading about the Continuous Tree, are you not feeling excited to read/explore more similar articles like Binary Tree and traversal algorithms like BFS and DFS Algorithm? Don't worry; Coding Ninjas has you covered. To learn, see Binary Tree, BFS, DFS and BFS vs DFS.
34+ registered 
