Find ancestors of given node in a Binary Tree

Find all ancestors of binary tree node

Here given code implementation process.

/*
  C Program 
+ Find ancestors of given node in a Binary Tree

*/
#include <stdio.h>

#include <stdlib.h>
 //structure of Binary Tree node
struct Node {
  int data;
  struct Node *left, *right;
};

struct Stack {
  struct Node *element;
  struct Stack *next;
};

//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes
struct Node *insert(int data) {
  //create dynamic memory to new binary tree node
  struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
  if (new_node != NULL) {
    //set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL; //Initially node right-pointer is NULL
  } else {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;

}
//Create a stack element and return this reference
struct Stack *push(struct Node *tree_node, struct Stack *head) {

  struct Stack *stack_node = (struct Stack *) malloc(sizeof(struct Stack));
  if (stack_node != NULL) {
    //set pointer values
    stack_node->element = tree_node;
    stack_node->next = head;

  } else {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  return stack_node;
}
//Remove stack elements
void pop(struct Stack **top) {
  if ( *top != NULL) {
    struct Stack *remove = *top;
    *top = remove->next;
    remove->element = NULL;
    remove->next = NULL;
    free(remove);
    remove = NULL;
  }
}
void showPath(struct Stack *temp) {

  if (temp != NULL) {
    showPath(temp->next);
    printf("%3d", temp->element->data);
  }
}
//Get all Ancestors of given node element 
void getAncestors(struct Node *root, struct Stack **head, int *status, int node) {
  if (root != NULL && *status == 0) {


    if (root->data == node) {

      if ( *head == NULL) {
        //When no Ancestor
        *status = -1;
        return;
      }

      *status = 1;
      showPath( *head);

      return;
    }

    //Add element into stack
    *head = push(root, *head);

    getAncestors(root->left, head, status, node);
    getAncestors(root->right, head, status, node);


    pop(head);

  }
}

void findAncestors(struct Node *root, int node) {

  struct Stack *head = NULL;

  int status = 0;

  printf("\nAncestor of node %d are : ", node);

  getAncestors(root, & head, & status, node);

  if (status == 0) {
    printf(" Node not exist");

  } else if (status == -1) {

    printf(" No Ancestor");
  }
}
int main() {

  struct Node *root = NULL;
  /* Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \       /
        7     8
       /     / \
      11    9   10
  */
  //Add element
  root = insert(1);
  root->left = insert(2);
  root->right = insert(3);
  root->right->right = insert(6);
  root->right->left = insert(5);
  root->left->left = insert(4);
  root->left->left->right = insert(7);
  root->right->right->left = insert(8);

  root->right->right->left->left = insert(9);
  root->right->right->left->right = insert(10);
  root->left->left->right->left = insert(11);
  //Test case
  findAncestors(root, 7);
  findAncestors(root, 10);
  findAncestors(root, 5);
  findAncestors(root, 1);
  findAncestors(root, 11);
  findAncestors(root, 12);
  return 0;
}

Output

Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist
/*
Java Program 
Find ancestors of given node in a Binary Tree
*/

#include<iostream>

using namespace std;
class Node {
  public:
  int data;
  Node *left, *right;
  Node(int value) {
    this->data = value;
    this->left = this->right = NULL;
  }
};
class MyStack {
  public:
  Node *element;
  MyStack *next;
  MyStack(Node *new_node, MyStack *head) {
    this->element = new_node;
    this->next = head;
  }
};
class BinaryTree {
  public:
  Node *root;
  MyStack *top;
  int flag;

  BinaryTree() {
    this->root = NULL;
    this->top = NULL;
    this->flag = 0;
  }
  void push(Node *tree_node) {
    this->top = new MyStack(tree_node, this->top);
  }
  void pop() {
    if (this->top != NULL) {
      MyStack *remove = this->top;
      this->top = remove->next;
      remove->element = NULL;
      remove->next = NULL;
      remove = NULL;
    }
  }
  void showPath(MyStack *head) {
    if (head != NULL) {
      this->showPath(head->next);
      cout << "  " << head->element->data;
    }
  }
  void getAncestors(Node *head, int node) {
    if (head != NULL && this->flag == 0) {
      if (head->data == node) {
        if (this->top == NULL) {
          this->flag = -1;
          return;
        }
        this->flag = 1;
        this->showPath(this->top);
        return;
      }
      this->push(head);
      this->getAncestors(head->left, node);
      this->getAncestors(head->right, node);
      this->pop();
    }
  }
  void findAncestors(int node) {
    this->flag = 0;
    cout << "\nAncestor of node "<< node <<" are : ";
    this->getAncestors(this->root, node);
    if (this->flag == 0) {
      cout << " Node not exist";
    } else
    if (this->flag == -1) {
      cout << " No Ancestor";
    }
  }
};

int main() {
  BinaryTree obj ;

  /* Make A Binary Tree
  -----------------------
        1
       /  \
      2    3
     /    /  \
    4    5    6
     \       /
      7     8
     /     / \
    11    9   10
  */
  obj.root = new Node(1);
  obj.root->left = new Node(2);
  obj.root->right = new Node(3);
  obj.root->right->right = new Node(6);
  obj.root->right->left = new Node(5);
  obj.root->left->left = new Node(4);
  obj.root->left->left->right = new Node(7);
  obj.root->right->right->left = new Node(8);
  obj.root->right->right->left->left = new Node(9);
  obj.root->right->right->left->right = new Node(10);
  obj.root->left->left->right->left = new Node(11);
  obj.findAncestors(7);
  obj.findAncestors(10);
  obj.findAncestors(5);
  obj.findAncestors(1);
  obj.findAncestors(11);
  obj.findAncestors(12);

  return 0;
}

Output

Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist
/*
Java Program 
Find ancestors of given node in a Binary Tree
*/

//Class of Binary Tree node
class Node {

  public int data;
  public Node left, right;
  //Make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = right = null;
  }
}

class MyStack {
  public Node element;
  public MyStack next;

  public MyStack(Node new_node, MyStack head) {
    element = new_node;
    next = head;
  }
}
public class BinaryTree {

  public Node root;

  public MyStack top;

  public int flag;

  public BinaryTree() {
    //Set initial initial values
    root = null;
    top = null;
    flag = 0;
  }


  //Create a MyStack element and return this reference
  public void push(Node tree_node) {

    top = new MyStack(tree_node, top);


  }

  //Remove MyStack elements
  public void pop() {
    if (top != null) {
      MyStack remove = top;
      top = remove.next;
      remove.element = null;
      remove.next = null;
      remove = null;
    }
  }

  public void showPath(MyStack head) {

    if (head != null) {
      showPath(head.next);
      System.out.print("  " + head.element.data);
    }
  }

  //Get all Ancestors of given node element 
  public void getAncestors(Node head, int node) {
    if (head != null && this.flag == 0) {


      if (head.data == node) {

        if (top == null) {
          //When no Ancestor
          this.flag = -1;
          return;
        }

        this.flag = 1;
        showPath(top);

        return;
      }

      //Add element into MyStack
      push(head);

      getAncestors(head.left, node);
      getAncestors(head.right, node);


      pop();

    }
  }

  public void findAncestors(int node) {


    this.flag = 0;

    System.out.print("\nAncestor of node " + node + " are : ");

    getAncestors(root, node);

    if (this.flag == 0) {
      System.out.print(" Node not exist");

    } else if (this.flag == -1) {

      System.out.print(" No Ancestor");
    }
  }
  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();

    /* Make A Binary Tree
      -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \       /
            7     8
           /     / \
          11    9   10
      */
    //Add element
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(6);
    obj.root.right.left = new Node(5);
    obj.root.left.left = new Node(4);
    obj.root.left.left.right = new Node(7);
    obj.root.right.right.left = new Node(8);

    obj.root.right.right.left.left = new Node(9);
    obj.root.right.right.left.right = new Node(10);
    obj.root.left.left.right.left = new Node(11);
    //Test case
    obj.findAncestors(7);
    obj.findAncestors(10);
    obj.findAncestors(5);
    obj.findAncestors(1);
    obj.findAncestors(11);
    obj.findAncestors(12);

  }
}

Output

Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist
/*
C# Program 
Find ancestors of given node in a Binary Tree
*/
using System;
//Class of Binary Tree node
public class Node {

  public int data;
  public Node left, right;
  //Make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = right = null;
  }
}

public class MyStack {
  public Node element;
  public MyStack next;

  public MyStack(Node new_node, MyStack head) {
    element = new_node;
    next = head;
  }
}
public class BinaryTree {

  public Node root;

  public MyStack top;

  public int flag;

  public BinaryTree() {
    //Set initial initial values
    root = null;
    top = null;
    flag = 0;
  }


  //Create a MyStack element and return this reference
  public void push(Node tree_node) {

    top = new MyStack(tree_node, top);


  }

  //Remove MyStack elements
  public void pop() {
    if (top != null) {
      MyStack remove = top;
      top = remove.next;
      remove.element = null;
      remove.next = null;
      remove = null;
    }
  }

  public void showPath(MyStack head) {

    if (head != null) {
      showPath(head.next);
      Console.Write("  " + head.element.data);
    }
  }

  //Get all Ancestors of given node element 
  public void getAncestors(Node head, int node) {
    if (head != null && this.flag == 0) {


      if (head.data == node) {

        if (top == null) {
          //When no Ancestor
          this.flag = -1;
          return;
        }

        this.flag = 1;
        showPath(top);

        return;
      }

      //Add element into MyStack
      push(head);

      getAncestors(head.left, node);
      getAncestors(head.right, node);


      pop();

    }
  }

  public void findAncestors(int node) {


    this.flag = 0;

    Console.Write("\nAncestor of node " + node + " are : ");

    getAncestors(root, node);

    if (this.flag == 0) {
      Console.Write(" Node not exist");

    } else if (this.flag == -1) {

      Console.Write(" No Ancestor");
    }
  }
  public static void Main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();

    /* Make A Binary Tree
      -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \       /
            7     8
           /     / \
          11    9   10
      */
    //Add element
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(6);
    obj.root.right.left = new Node(5);
    obj.root.left.left = new Node(4);
    obj.root.left.left.right = new Node(7);
    obj.root.right.right.left = new Node(8);

    obj.root.right.right.left.left = new Node(9);
    obj.root.right.right.left.right = new Node(10);
    obj.root.left.left.right.left = new Node(11);
    //Test case
    obj.findAncestors(7);
    obj.findAncestors(10);
    obj.findAncestors(5);
    obj.findAncestors(1);
    obj.findAncestors(11);
    obj.findAncestors(12);

  }
}

Output

Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist
#Python3 Program 
#Find ancestors of given node in a Binary Tree

class Node :

  def __init__(self, value) :
    self.data = value;
    self.left = self.right = None;
  

class MyStack :

  def __init__(self, new_node, head) :
    self.element = new_node;
    self.next = head;
  

class BinaryTree :
  def __init__(self) :
    self.root = None;
    self.top = None;
    self.flag = 0;
  
  def push(self, tree_node) :
    self.top = MyStack(tree_node, self.top);
  
  def pop(self) :
    if (self.top != None) :
      remove = self.top;
      self.top = remove.next;
      remove.element = None;
      remove.next = None;
      remove = None;
    
  
  def showPath(self, head) :
    if (head != None) :
      self.showPath(head.next);
      print(head.element.data,end=" ");
    
  
  def getAncestors(self, head, node) :
    if (head != None and self.flag == 0) :
      if (head.data == node) :
        if (self.top == None) :
          self.flag = -1;
          return;
        
        self.flag = 1;
        self.showPath(self.top);
        return;
      
      self.push(head);
      self.getAncestors(head.left, node);
      self.getAncestors(head.right, node);
      self.pop();
    
  
  def findAncestors(self, node) :
    self.flag = 0;
    print("\nAncestor of node ", node ," are : ",end=" ");
    self.getAncestors(self.root, node);
    if (self.flag == 0) :
      print(" Node not exist",end=" ");
    elif (self.flag == -1) :
      print(" No Ancestor",end=" ");
    
  
def main() :
  obj = BinaryTree();

  # Make A Binary Tree
  #        1
  #       /  \
  #      2    3
  #     /    /  \
  #    4    5    6
  #     \       /
  #      7     8
  #     /     / \
  #    11    9   10
  #  
  obj.root = Node(1);
  obj.root.left = Node(2);
  obj.root.right = Node(3);
  obj.root.right.right = Node(6);
  obj.root.right.left = Node(5);
  obj.root.left.left = Node(4);
  obj.root.left.left.right = Node(7);
  obj.root.right.right.left = Node(8);
  obj.root.right.right.left.left = Node(9);
  obj.root.right.right.left.right = Node(10);
  obj.root.left.left.right.left = Node(11);
  obj.findAncestors(7);
  obj.findAncestors(10);
  obj.findAncestors(5);
  obj.findAncestors(1);
  obj.findAncestors(11);
  obj.findAncestors(12);
  

if __name__ == "__main__":
  main()

Output

Ancestor of node  7  are :  1 2 4 
Ancestor of node  10  are :  1 3 6 8 
Ancestor of node  5  are :  1 3 
Ancestor of node  1  are :   No Ancestor 
Ancestor of node  11  are :  1 2 4 7 
Ancestor of node  12  are :   Node not exist 
#Ruby Program 
#Find ancestors of given node in a Binary Tree
class Node 
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right
  def initialize(value) 
    @data = value
    @left = @right = nil
  end
end

class MyStack 
  attr_reader :element, :next
  attr_accessor :element, :next
  def initialize(new_node, head) 
    @element = new_node
    @next = head
  end
end

class BinaryTree 
  attr_reader :root, :top, :flag
  attr_accessor :root, :top, :flag
  def initialize() 
    @root = nil
    @top = nil
    @flag = 0
  end
  def push(tree_node) 
    @top = MyStack.new(tree_node, @top)
  end
  def pop() 
    if (@top != nil) 
      remove = @top
      @top = remove.next
      remove.element = nil
      remove.next = nil
      remove = nil
    end
  end
  def showPath(head) 
    if (head != nil) 
      self.showPath(head.next)
      print("  ", head.element.data)
    end
  end
  def getAncestors(head, node) 
    if (head != nil and self.flag == 0) 
      if (head.data == node) 
        if (@top == nil) 
          self.flag = -1
          return
        end
        self.flag = 1
        self.showPath(@top)
        return
      end
      self.push(head)
      self.getAncestors(head.left, node)
      self.getAncestors(head.right, node)
      self.pop()
    end
  end
  def findAncestors(node) 
    self.flag = 0
    print("\nAncestor of node ", node , " are  :")
    self.getAncestors(@root, node)
    if (self.flag == 0) 
      print(" Node not exist")
    elsif (self.flag == -1) 
      print(" No Ancestor")
    end
  end

end


def main() 
  obj = BinaryTree.new()
  # Make A Binary Tree
  #        1
  #       /  \
  #      2    3
  #     /    /  \
  #    4    5    6
  #     \       /
  #      7     8
  #     /     / \
  #    11    9   10
  # 
  obj.root = Node.new(1)
  obj.root.left = Node.new(2)
  obj.root.right = Node.new(3)
  obj.root.right.right = Node.new(6)
  obj.root.right.left = Node.new(5)
  obj.root.left.left = Node.new(4)
  obj.root.left.left.right = Node.new(7)
  obj.root.right.right.left = Node.new(8)
  obj.root.right.right.left.left = Node.new(9)
  obj.root.right.right.left.right = Node.new(10)
  obj.root.left.left.right.left = Node.new(11)
  obj.findAncestors(7)
  obj.findAncestors(10)
  obj.findAncestors(5)
  obj.findAncestors(1)
  obj.findAncestors(11)
  obj.findAncestors(12)
end
main()

Output

Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist
<?php
/*
  Php Program
  Find ancestors of given node in a Binary Tree
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = $this->right = null;
  }
}
class MyStack {
  public $element;
  public $next;

  function __construct($new_node, $head) {
    $this->element = $new_node;
    $this->next = $head;
  }
}
class BinaryTree {
  public $root;
  public $top;
  public $flag;

  function __construct() {
    $this->root = null;
    $this->top = null;
    $this->flag = 0;
  }
  public  function push($tree_node) {
    $this->top = new MyStack($tree_node, $this->top);
  }
  public  function pop() {
    if ($this->top != null) {
      $remove = $this->top;
      $this->top = $remove->next;
      $remove->element = null;
      $remove->next = null;
      $remove = null;
    }
  }
  public  function showPath($head) {
    if ($head != null) {
      $this->showPath($head->next);
      echo("  ". $head->element->data);
    }
  }
  public  function getAncestors($head, $node) {
    if ($head != null && $this->flag == 0) {
      if ($head->data == $node) {
        if ($this->top == null) {
          $this->flag = -1;
          return;
        }
        $this->flag = 1;
        $this->showPath($this->top);
        return;
      }
      $this->push($head);
      $this->getAncestors($head->left, $node);
      $this->getAncestors($head->right, $node);
      $this->pop();
    }
  }
  public  function findAncestors($node) {
    $this->flag = 0;
    echo("\nAncestor of node ". $node ." are : ");
    $this->getAncestors($this->root, $node);
    if ($this->flag == 0) {
      echo(" Node not exist");
    } else
    if ($this->flag == -1) {
      echo(" No Ancestor");
    }
  }
}
function main() {
  $obj = new BinaryTree();
  /* Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \       /
        7     8
       /     / \
      11    9   10
  */
  $obj->root = new Node(1);
  $obj->root->left = new Node(2);
  $obj->root->right = new Node(3);
  $obj->root->right->right = new Node(6);
  $obj->root->right->left = new Node(5);
  $obj->root->left->left = new Node(4);
  $obj->root->left->left->right = new Node(7);
  $obj->root->right->right->left = new Node(8);
  $obj->root->right->right->left->left = new Node(9);
  $obj->root->right->right->left->right = new Node(10);
  $obj->root->left->left->right->left = new Node(11);
  $obj->findAncestors(7);
  $obj->findAncestors(10);
  $obj->findAncestors(5);
  $obj->findAncestors(1);
  $obj->findAncestors(11);
  $obj->findAncestors(12);
}
main();

Output

Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist
/*
  Node JS Program
  Find ancestors of given node in a Binary Tree
*/
class Node {
  
  constructor(value) {
    this.data = value;
    this.left = this.right = null;
  }
}
class MyStack {
  
  constructor(new_node, head) {
    this.element = new_node;
    this.next = head;
  }
}
class BinaryTree {
  
  constructor() {
    this.root = null;
    this.top = null;
    this.flag = 0;
  }
  push(tree_node) {
    this.top = new MyStack(tree_node, this.top);
  }
  pop() {
    if (this.top != null) {
      var remove = this.top;
      this.top = remove.next;
      remove.element = null;
      remove.next = null;
      remove = null;
    }
  }
  showPath(head) {
    if (head != null) {
      this.showPath(head.next);
      process.stdout.write("  " + head.element.data);
    }
  }
  getAncestors(head, node) {
    if (head != null && this.flag == 0) {
      if (head.data == node) {
        if (this.top == null) {
          this.flag = -1;
          return;
        }
        this.flag = 1;
        this.showPath(this.top);
        return;
      }
      this.push(head);
      this.getAncestors(head.left, node);
      this.getAncestors(head.right, node);
      this.pop();
    }
  }
  findAncestors(node) {
    this.flag = 0;
    process.stdout.write("\nAncestor of node " + node + " are : ");
    this.getAncestors(this.root, node);
    if (this.flag == 0) {
      process.stdout.write(" Node not exist");
    } else
    if (this.flag == -1) {
      process.stdout.write(" No Ancestor");
    }
  }
}

function main() {
  var obj = new BinaryTree();
  /* Make A Binary Tree
    -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \       /
        7     8
       /     / \
      11    9   10
    */
  obj.root = new Node(1);
  obj.root.left = new Node(2);
  obj.root.right = new Node(3);
  obj.root.right.right = new Node(6);
  obj.root.right.left = new Node(5);
  obj.root.left.left = new Node(4);
  obj.root.left.left.right = new Node(7);
  obj.root.right.right.left = new Node(8);
  obj.root.right.right.left.left = new Node(9);
  obj.root.right.right.left.right = new Node(10);
  obj.root.left.left.right.left = new Node(11);
  obj.findAncestors(7);
  obj.findAncestors(10);
  obj.findAncestors(5);
  obj.findAncestors(1);
  obj.findAncestors(11);
  obj.findAncestors(12);
}
main();

Output

Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist
/*
  Swift 4 Program
  Find ancestors of given node in a Binary Tree
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;

  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class MyStack {
  var element: Node? ;
  var next: MyStack? ;
  init(_ new_node: Node? , _ head : MyStack? ) {
    self.element = new_node;
    self.next = head;
  }
}
class BinaryTree {
  var root: Node? ;
  var top: MyStack? ;
  var flag: Int;
  init() {
    self.root = nil;
    self.top = nil;
    self.flag = 0;
  }
  func push(_ tree_node: Node? ) {
    self.top = MyStack(tree_node, self.top);
  }
  func pop() {
    if (self.top != nil) {
      var remove: MyStack? = self.top;
      self.top = remove!.next;
      remove!.element = nil;
      remove!.next = nil;
      remove = nil;
    }
  }
  func showPath(_ head: MyStack? ) {
    if (head != nil) {
      self.showPath(head!.next);
      let temp: Node? = head!.element;
      print(temp!.data, terminator : " ");
    }
  }
  func getAncestors(_ head: Node? , _ node : Int) {
    if (head != nil && self.flag == 0) {
      if (head!.data == node) {
        if (self.top == nil) {
          self.flag = -1;
          return;
        }
        self.flag = 1;
        self.showPath(self.top);
        return;
      }
      self.push(head);
      self.getAncestors(head!.left, node);
      self.getAncestors(head!.right, node);
      self.pop();
    }
  }
  func findAncestors(_ node: Int) {
    self.flag = 0;
    print("\nAncestor of node ", node , " are : ", terminator : " ");
    self.getAncestors(self.root, node);
    if (self.flag == 0) {
      print(" Node not exist", terminator : " ");
    } else
    if (self.flag == -1) {
      print(" No Ancestor", terminator : " ");
    }
  }
}
func main() {
  let obj: BinaryTree = BinaryTree();

  /* Make A Binary Tree
  -----------------------
        1
       /  \
      2    3
     /    /  \
    4    5    6
     \       /
      7     8
     /     / \
    11    9   10
  */
  obj.root = Node(1);
  obj.root!.left = Node(2);
  obj.root!.right = Node(3);
  obj.root!.right!.right = Node(6);
  obj.root!.right!.left = Node(5);
  obj.root!.left!.left = Node(4);
  obj.root!.left!.left!.right = Node(7);
  obj.root!.right!.right!.left = Node(8);
  obj.root!.right!.right!.left!.left = Node(9);
  obj.root!.right!.right!.left!.right = Node(10);
  obj.root!.left!.left!.right!.left = Node(11);
  obj.findAncestors(7);
  obj.findAncestors(10);
  obj.findAncestors(5);
  obj.findAncestors(1);
  obj.findAncestors(11);
  obj.findAncestors(12);
}
main();

Output

Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved