Continuous Tree | C ++ program to check if a tree is continuous or not ; A binary tree node has data , pointer to left child and a pointer to right child ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Function to check tree is continuous or not ; if next node is empty then return true ; if current node is leaf node then return true because it is end of root to leaf path ; If left subtree is empty , then only check right ; If right subtree is empty , then only check left ; If both left and right subtrees are not empty , check everything ; Driver program to test mirror ( )
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } bool treeContinuous ( struct Node * 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 ) && treeContinuous ( ptr -> right ) ; if ( ptr -> right == NULL ) return ( abs ( ptr -> data - ptr -> left -> data ) == 1 ) && treeContinuous ( ptr -> left ) ; return abs ( ptr -> data - ptr -> left -> data ) == 1 && abs ( ptr -> data - ptr -> right -> data ) == 1 && treeContinuous ( ptr -> left ) && treeContinuous ( ptr -> right ) ; } int main ( ) { struct Node * root = newNode ( 3 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 4 ) ; root -> left -> left = newNode ( 1 ) ; root -> left -> right = newNode ( 3 ) ; root -> right -> right = newNode ( 5 ) ; treeContinuous ( root ) ? cout << " Yes " : cout << " No " ; return 0 ; }