Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Algorithm
3.
Code Implementation
3.1.
Input  
3.2.
Output 
4.
Time complexity
5.
Space complexity
6.
Frequently Asked Questions
6.1.
What do you mean by continuous trees? 
6.2.
How are contiguous storage trees implemented? 
6.3.
What is a full binary tree, exactly? 
6.4.
What is the method for storing trees in memory? 
6.5.
What exactly is a null tree? 
7.
Conclusion
Last Updated: Mar 27, 2024

Continuous Tree

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

A Continuous Tree is a tree in which the difference in absolute value between the parent node and all of its immediate children nodes is always one.

If we choose any node along the path from the root to the leaf, then:

  • |weight of node-weight of left child node| = 1
     
  • |weight of node-weight of right child node| = 1.

Qualified for being a Continuous Tree - 

 

Not qualified for being a Continuous Tree -

Must Recommended Topic, Binary Tree Postorder Traversal.

Algorithm

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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)

Check out this problem - Mirror A Binary Tree

Space complexity

O(N) The tree's space complexity is proportional to the number of nodes in the tree.

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

What do you mean by continuous trees? 

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 TreeBFSDFS and BFS vs DFS.

Upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and more with our Coding Ninjas Studio Guided Path! Check out the mock test series and enter the contests hosted by Coding Ninjas Studio if you want to put your coding skills to the test! However, if you're just getting started and want to know what questions tech giants like Amazon, Microsoft, and Uber ask, you should look at the difficulties, interview experiences, and interview bundle for placement preparations. 

Nonetheless, you may want to try our premium courses to give your career a leg up on the competition! 

If you find our blogs to be useful and fascinating, please vote them up!

Happy Learning!

Live masterclass