ינאָרדער סאַקסעסער פון אַ נאָדע אין ביינערי בוים  


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַמאַזאָן עקספּעדיאַ מאָרגאַן סטאַנלי OYO רומז Snapchat
ביינערי זוכן בוים בוים

פּראָבלעם סטאַטעמענט  

די פּראָבלעם פרעגט צו געפֿינען "ינאָרדער סאַקסעסער פון אַ נאָדע אין ביינערי טרי". א ינאָרדער סאַקסעסער פון אַ נאָדע איז אַ נאָדע אין די ביינערי בוים וואָס קומט נאָך די געגעבן נאָדע אין די ינאָרדער דורך די געגעבן ביינערי בוים.

בייַשפּיל  

שפּילקע  

Inorder successor of 6 is 4

דערקלערונג

די ינאָרדער טראַווערסאַל פון דעם בוים איז 9 7 1 6 4 5 3. אזוי דער ינאָרדער סאַקסעסער פון 1 איז 6.

צוגאַנג  

אין אַלגעמיין, מיר זענען געזאָגט צו געפֿינען די ווייַטער נאָדע אין די אָרדערינג דורך אַ ביינערי זוכן בוים. אָבער דאָס איז אַנדערש פון אַ ביינערי בוים. איין זאַך וואָס מיר זאָל באַמערקן איז אַז די ינאָרדער טראַווערסאַל פון אַ אַלגעמיין ביינערי בוים איז נישט אין אַסענדינג סדר. איצט לאָזן ס פאָרויס. אַזוי אויב מיר האָבן אַ נאָדע, עס זענען 3 קאַסעס וואָס מיר זאָל קוקן אויף.

די 3 קאַסעס וואָס מיר זאָלן באַמערקן זענען פארבונדן צו זיין רעכט קינד אָדער אויב די קראַנט נאָדע זיך איז אַ רעכט קינד. אַזוי אויב די נאָדע האט אַ רעכט קינד. דער אָרדער סאַקסעסער איז סימפּלי די לינקס קינד אין זיין רעכט סאַבסטרי. אבער אויב עס טוט נישט האָבן די רעכט קינד. דערנאָך געפֿינען די לאָואַסט אָוועס פון די געגעבן נאָדע אַזוי אַז דער געגעבן נאָדע ליגט אין די לינקס סובטרעמע פון ​​די אָוועס. אויב איר טאָן דאָס, רעקורסיוועלי געפֿינען די נאָדע, און ווען מיר מאַך צוריק פון רעקורסיאָן קראָם, דער פאָטער פון וואו מיר האָבן אויסדערוויילט די לינקס ריכטונג.

זע אויך
געפֿינען די קלאָוסאַסט פּאַלינדראָמע נומער

איצט די לעצטע פאַל איז אויב די נאָדע איז די רעכט קינד. אויב דאָס כאַפּאַנז, עס איז קיין ינאָרדער סאַקסעסער פֿאַר די נאָדע.

קאָדעקס  

C ++ קאָד צו געפֿינען ינאָרדער סאַקסעסער פון אַ נאָדע אין ביינערי בוים

#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* findLeftMostNode(node* root){
  while(root && root->left) root = root->left;
  return root;
}

node* findRightMostNode(node* root){
  while(root && root->right) root = root->right;
  return root;
}

node* findAncestorSuccessor(node* root, node* given)
{
  if(root){
    if(root == given)
      return root;
    node* tmp = findAncestorSuccessor(root->left, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
    tmp = findAncestorSuccessor(root->right, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
  }
    return NULL;
}

void findInorderSuccesor(node* root, node* given)
{
    // if right child exists
    if(given->right)
    {
    	node* leftmost = findLeftMostNode(given);
    	cout<<"Inorder Succesor of "<<given->data<<" is "<<leftmost->data;
    	return;
    }
    // if right child does not exists
    if(given->right == NULL)
    {
        node* rightmost = findRightMostNode(root);
        if(rightmost == given)
            cout<<"Inorder Successor does not exists";
        else
        	findAncestorSuccessor(root, given);
    }
}

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);
  root->left->right->right = create(4);
  findInorderSuccesor(root, root->left->right->left);
}
Inorder Successor of 1 is 6

Java קאָד צו געפֿינען ינאָרדער סאַקסעסער פון אַ נאָדע אין ביינערי טרי

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 findLeftMostNode(node root){
    while(root != null && root.left != null) root = root.left;
    return root;
  }

  static node findRightMostNode(node root){
    while(root != null && root.right != null) root = root.right;
    return root;
  }

  static node findAncestorSuccessor(node root, node given)
  {
    if(root != null){
      if(root == given)
        return root;
      node tmp = findAncestorSuccessor(root.left, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
      tmp = findAncestorSuccessor(root.right, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
    }
      return null;
  }

  static void findInorderSuccesor(node root, node given)
  {
      // if right child exists
      if(given.right != null)
      {
      	node leftmost = findLeftMostNode(given);
      	System.out.print("Inorder Successor of "+given.data+" is "+leftmost.data);
      	return;
      }
      // if right child does not exists
      else
      {
          node rightmost = findRightMostNode(root);
          if(rightmost == given)
              System.out.print("Inorder Successor does not exists");
          else
          	findAncestorSuccessor(root, given);
      }
  }

  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);
    root.left.right.right = create(4);
    findInorderSuccesor(root, root.left.right.left);
  }
}
Inorder Successor of 1 is 6

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (N), ווייַל אין ערגסט פאלן מיר קען האָבן צו פאָרן איבער אַלע די נאָודז.

זע אויך
באַפרייַען אַ ביינערי זוכן בוים

ספעיס קאַמפּלעקסיטי

אָ (ה), ווייַל מיר האָבן געוויינט רעקורסיאָן. אַזוי אויב מיר באַטראַכטן די פּלאַץ גענומען דורך קאַמפּיילער אָנלייגן. די פּלאַץ קאַמפּלעקסיטי איז אָפענגיק אויף דער הייך פון דעם בוים.