jain12

Check if each internal node of a BST has exactly one child

Mar 11th, 2020
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.84 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. class Node{
  4. public:
  5. int data;
  6. Node *left,*right;
  7. Node(int key){
  8. data=key;
  9. left=right=NULL;
  10. }
  11. };
  12.  
  13. void Insert(Node **root_ref,int key){
  14. if(*root_ref==NULL){
  15. *root_ref=new Node(key);
  16. return;
  17. }
  18. if((*root_ref)->data<key)
  19. Insert(&((*root_ref)->right),key);
  20. else
  21. if((*root_ref)->data>key)
  22. Insert(&((*root_ref)->left),key);
  23. }
  24.  
  25. int HasOnlyOneChild(Node *root){
  26. if(root==NULL)
  27. return 1;
  28. if(root->left!=NULL && root->right!=NULL)
  29. return 0;
  30. return HasOnlyOneChild(root->left)&& HasOnlyOneChild(root->right);
  31. }
  32.  
  33. int main(){
  34. Node *root=NULL;
  35. Insert(&root,5);
  36. Insert(&root,7);
  37. Insert(&root,4);
  38. Insert(&root,8);
  39. if(HasOnlyOneChild(root))
  40. cout<<"yes";
  41. else
  42. cout<<"no";
  43. return 0;
  44. }
Add Comment
Please, Sign In to add comment