బైనరీ చెట్టు ఇచ్చినట్లయితే, మీరు అన్ని సగం నోడ్లను ఎలా తొలగిస్తారు?


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అకోలైట్ అమెజాన్ మైక్రోసాఫ్ట్ PayU స్నాప్డీల్ Synopsys యాహూ
ట్రీ

సమస్య “బైనరీ చెట్టు ఇచ్చినట్లయితే, మీరు అన్ని సగం నోడ్‌లను ఎలా తొలగిస్తారు?” మీకు బైనరీ చెట్టు ఇవ్వబడిందని పేర్కొంది. ఇప్పుడు మీరు సగం నోడ్లను తొలగించాలి. సగం నోడ్ చెట్టులో ఒకే బిడ్డను కలిగి ఉన్న నోడ్గా నిర్వచించబడింది. గాని అది ఎడమ బిడ్డ లేదా కుడి బిడ్డ.

ఉదాహరణ

బైనరీ చెట్టు ఇచ్చినట్లయితే, మీరు అన్ని సగం నోడ్లను ఎలా తొలగిస్తారు?

Inorder Traversal of tree after half nodes removal: 5 3 6 2 7

వివరణ

విలువ 4 ఉన్న నోడ్‌కు ఒకే ఎడమ బిడ్డ ఉంది. అందువలన ఇది బైనరీ చెట్టు నుండి తొలగించబడింది మరియు దాని ఎడమ బిడ్డ చెట్టు పైకి కదిలింది. ఎందుకంటే ఒకటిన్నర నోడ్ మాత్రమే ఉంది. దాని తొలగింపు తరువాత, మనకు చెట్టు మిగిలి ఉంది, దీని ఇనార్డర్ ట్రావెర్సల్ అవుట్‌పుట్‌గా ముద్రించబడింది.

అప్రోచ్

సమస్య ఒక ఇచ్చింది బైనరీ చెట్టు, మీరు అన్ని సగం నోడ్‌లను ఎలా తొలగిస్తారు? ద్రావణంలోకి దూకడానికి ముందు. సగం నోడ్ అంటే ఏమిటో మనం మొదట తెలుసుకోవాలి? సగం నోడ్ అనేది ఒకే బిడ్డను కలిగి ఉన్న బైనరీ చెట్టులోని నోడ్. అందువల్ల పిల్లవాడు లేదా ఇద్దరు పిల్లలు లేని నోడ్ సగం నోడ్గా పరిగణించబడదు. ఇప్పటి నుండి సగం నోడ్ అంటే ఏమిటో మనకు తెలుసు. సమస్యకు పరిష్కారంతో మనం ముందుకు సాగాలి. పరిష్కారం సులభం. మేము చెట్టును దాటుకుంటాము మరియు సగం నోడ్ను కనుగొన్నప్పుడల్లా దాని బిడ్డతో భర్తీ చేస్తాము. ఎడమ పిల్లవాడు ఉన్నాడా మరియు కుడి బిడ్డ శూన్యమా అని మేము తనిఖీ చేస్తాము. అప్పుడు మేము పేరెంట్ (లేదా సగం నోడ్) ను దాని ఎడమ బిడ్డతో భర్తీ చేస్తాము. అదేవిధంగా, సరైన పిల్లవాడు మాత్రమే సంతానం అయితే. సరైన పిల్లవాడు పేరెంట్ నోడ్‌ను భర్తీ చేస్తుంది.

కోడ్

అన్ని సగం నోడ్‌లను తొలగించడానికి సి ++ కోడ్

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

node* removeHalfNode(node* &root){
    if(!root)
        return NULL;
    if(root->left == NULL && root->right != NULL)
        root = removeHalfNode(root->right);
    else if(root->left != NULL && root->right == NULL)
        root = removeHalfNode(root->left);
    else {
        removeHalfNode(root->left);
        removeHalfNode(root->right);
    }
    return root;
}

void inorder(node* root){
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);

  cout<<"Inorder traversal before removing the half nodes"<<endl;
  inorder(root);
  cout<<endl<<"Inorder traversal after removing the half nodes"<<endl;
  root = removeHalfNode(root);
  inorder(root);
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3
Inorder traversal after removing the half nodes
9 7 1 5 3

అన్ని సగం నోడ్‌లను తొలగించడానికి జావా కోడ్

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static node removeHalfNode(node root){
      if(root == null)
          return null;
      root.left = removeHalfNode(root.left); 
        root.right = removeHalfNode(root.right); 
   
        if(root.left == null && root.right == null) 
            return root;
        if(root.left == null){ 
            node Node = root.right;
            return Node;
        }
        if(root.right == null){ 
            node Node = root.left;
            return Node;
        } 
        return root;
  }

  static void inorder(node root){
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);

    System.out.println("Inorder traversal before removing the half nodes");
    inorder(root);
    System.out.println("\nInorder traversal after removing the half nodes");
    root = removeHalfNode(root);
    inorder(root);
  }
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3 
Inorder traversal after removing the half nodes
9 7 1 5 3

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఎందుకంటే మేము బైనరీ చెట్టులోని అన్ని నోడ్ల మీదుగా ప్రయాణించాము. సమయం సంక్లిష్టత సరళమైనది.

అంతరిక్ష సంక్లిష్టత

ఓ (హెచ్), అల్గోరిథం ఒక పునరావృత అల్గోరిథం. అందువల్ల స్థల సంక్లిష్టత కంపైలర్ స్టాక్ మీద ఆధారపడి ఉంటుంది, ఇది చెట్టు యొక్క ఎత్తుపై ఆధారపడి ఉంటుంది.