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


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן פאָורקיטעס גוגל InfoEdge מאָרגאַן סטאַנלי Paytm סאַמסונג
אָנלייגן בוים

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

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

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

בייַשפּיל

אַרייַנשרייַב 

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

שליסל = 6

5 2 1

דערקלערונג: דער דרך פון די שורש צו די נאָדע מיט ווערט 6 איז 1 2 5 6. אַזוי דער פאָטער סיקוואַנס פון 6 צו וואָרצל איז 5 2 1.

אַרייַנשרייַב:

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

שליסל = 10

9 7 1

אַלגאָריטהם

1. Create a structure Node which contains an integer variable to hold data and two pointers left and right of type Node.
2. After that, create the parameterized constructor of the structure which accepts an integer value as it's parameter. Store the integer value in the data variable of Node and initialize left and right pointers as null.
3. Create a function to print the tree path which accepts an unordered map and an integer variable key as it's a parameter. While the key variable is equal to the map[key], print the key.
4. Similarly, create another function to set the parents for all the nodes in the given binary tree which accepts a pointer to the root node and an unordered map as it's parameter.
5. Create a stack data structure of Node* type. Push/insert the root in the stack.
6. After that, traverse while the size of the stack is not 0. Create a pointer curr of type Node and store the element at the top of the stack in it and pop/delete it from the stack.
7. If the right of the curr is present, update the map at index data of right of curr as the data of curr. Push/insert the right of curr in the stack.
8. If the left of the curr is present, update the map at index data of the left of curr as the data of curr. Push/insert the left of curr in the stack.
9. Similarly, create another function to print the ancestors. Check if the root is equal to null, return.
10. Create an unordered map and set the data of its root as 0.
11. Call the function to set the parents of all nodes.
12. Finally, call the function to print the tree path.

דאָ פֿאַר דעם פּראָבלעם מיר באַקומען אַ ביינערי בוים און מיר דאַרפֿן צו דרוקן אָוועס פון אַ נאָדע. פּונקט ווי מיר האָבן קינדער פון אַ נאָדע, מיר האָבן זיין אָוועס אַחוץ דער וואָרצל פון דעם בוים. אויב איר באַטראַכטן די בלעטער פון אַ בוים, זיי טאָן ניט האָבן קינדער. סימילאַרלי, דער וואָרצל נאָדע האט נישט אַן אָוועס. דאָ מיר קראָם די פאָטער פון יעדער נאָדע. אַזוי אַז ווען מיר דאַרפֿן צו דרוקן זייַן אָוועס. מיר וועלן נוצן די עלטערן צו געפֿינען זייער אָוועס. מיר האָבן געוויינט אַן ונאָרדערעד_מאַפּ / האַשסעט צו דורכפירן דעם אָפּעראַציע. זינט די HashSet אַלאַוז די ינסערשאַן / שאַרף / דילישאַן אין O (1). מיר קענען סאָלווע דעם פּראָבלעם אין לינעאַר צייט קאַמפּלעקסיטי. אין די לייזונג אונטן, מיר נוצן אַ גראַפיק זוכן ווי אַ צוגאַנג צו דורך דער גאנצער בוים. און בשעת טראַווערסינג, מיר סטאָרד די פאָטער פון יעדער נאָדע. דערנאָך מיר האָבן באשאפן אַ פאַנגקשאַנז בשעת מיר פאָרן איבער אונדזער מאַפּע (וואָס סטאָרז די עלטערן) צו דרוקן די אָוועס. די גאנצע לייזונג ראַנז אין לינעאַר צייט קאַמפּלעקסיטי פון אָ (N).

קאָדעקס

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

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

struct Node{
    int data;
    Node *left, *right;

    Node(int data){
        this->data = data;
        this->left = this->right = nullptr;
  }
};

void printTopToBottomPath(unordered_map<int, int> parent, int key){
    while(key = parent[key]){
        cout << key << " ";
    }
    cout << endl;
}

void setParent(Node* root, unordered_map<int, int> &parent){
    
    stack<Node*> stack;
    stack.push(root);

    while(!stack.empty()){
        
        Node* curr = stack.top();
        stack.pop();

        if(curr->right){
           parent[curr->right->data] = curr->data;
           stack.push(curr->right);
        }

        if(curr->left){
           parent[curr->left->data] = curr->data;
           stack.push(curr->left);
        }
    }
}

void printAncestors(Node* root, int node){
    
    if(root == nullptr){
        return;
    }

    unordered_map<int, int> parent;

    parent[root->data] = 0;

    setParent(root, parent);

    printTopToBottomPath(parent, node);
}

int main(){
    Node* root = nullptr;

    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(7);
    root->left->left = new Node(3);
    root->left->right = new Node(5);
    root->right->left = new Node(8);
    root->right->right = new Node(9);
    root->left->left->left = new Node(4);
    root->left->right->right = new Node(6);
    root->right->right->left = new Node(10);

    int key = 6;
    printAncestors(root, key);

    return 0;
}
5 2 1

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

import java.util.*;

class Node{
  int data;
  Node left = null, right = null;

  Node(int data){
    this.data = data;
  }
}

class Main{
  
  public static void printTopToBottomPath(Map<Integer, Integer> parent, int key){
    while((key = parent.get(key)) != 0){
      System.out.print(key + " ");
    }
  }

  public static void setParent(Node root, Map<Integer, Integer> parent){
    
    Deque<Node> stack = new ArrayDeque<>();
    stack.add(root);

    while(!stack.isEmpty()){
      
      Node curr = stack.pollLast();

      if(curr.right != null){
        parent.put(curr.right.data, curr.data);
        stack.add(curr.right);
      }

      if(curr.left != null){
        parent.put(curr.left.data, curr.data);
        stack.add(curr.left);
      }
    }
  }

  public static void printAncestors(Node root, int node){
    
    if(root == null){
      return;
    }

    Map<Integer, Integer> parent = new HashMap<>();

    parent.put(root.data, 0);

    setParent(root, parent);

    printTopToBottomPath(parent, node);
  }

  public static void main(String[] args){
      
      Node root = new Node(1);
      root.left = new Node(2);
            root.right = new Node(7);
            root.left.left = new Node(3);
            root.left.right = new Node(5);
            root.right.left = new Node(8);
            root.right.right = new Node(9);
            root.left.left.left = new Node(4);
            root.left.right.right = new Node(6);
            root.right.right.left = new Node(10);

      int key = 6;
    
      printAncestors(root, key);
  }
}
5 2 1

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

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

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

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

אָ (N) ווייַל מיר געוויינט עקסטרע פּלאַץ אין ונאָרדערעד_מאַפּ און אָנלייגן.