Implement Threaded Binary Search Tree

Node insertion in a threaded binary search tree

Here given code implementation process.

//C Program 
//Implement Threaded Binary Search Tree
#include <stdio.h>
#include <stdlib.h>

//Structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};


struct Node* create_node(int data,
  struct Node*left_node,
  struct Node*right_node)
{
  //Create a dynamic node of binary search tree 
  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 = left_node; 
    new_node->right = right_node;
  }
  else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  return new_node;
}

//Adding a new node in Threaded Binary Search Tree
struct Node* add_node( struct Node *root, 
  struct Node*left_node,
  struct Node*right_node,
  int data)
{

  if(root!=NULL )
  {

    if(root->data >= data)
    {
      if(root->left==left_node)
      {
        root->left = create_node(data,left_node,root);
      }
      else
      {
        root->left = add_node(root->left,left_node,root,data);
      }
    }
    else if(root->data < data)
    {
      if(root->right==right_node)
      {
        root->right = create_node(data,root,right_node);
      }
      else
      {
        root->right = add_node(root->right,root,right_node,data);
      }
    }
    return root;
  }
  else
  {
    return create_node(data,left_node,right_node);
  }

}
//Handling the request of new node insertion 
struct Node* add(struct Node*root,int data)
{
  return add_node(root,NULL,NULL,data);
}

//Recursive inorder traversal Threaded Binary Search Tree
void inorder(struct Node*root,
  struct Node*left_node,
  struct Node*right_node)
{

  if(root!=NULL)
  {
    if(root->left!=left_node)
    {
      inorder(root->left,left_node,root);
    }  

    printf("%3d",root->data );

    if(root->right != right_node)
    {
      inorder(root->right,root,right_node);
    }
  }

}
int main()
{

  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
         5
       /    \
      3      9
     / \     / \
    1   4   8   11
   / \     /      \
  -3  2   7        12


  */                


  root  = add(root,5); 
  add(root,3); 
  add(root,9); 
  add(root,1); 
  add(root,4); 
  add(root,8); 
  add(root,11); 
  add(root,-3); 
  add(root,2); 
  add(root,7); 
  add(root,12); 

  inorder(root,NULL,NULL);

  return 0;
}

Output

 -3  1  2  3  4  5  7  8  9 11 12
//C++ Program 
//Implement Threaded Binary Search Tree
#include <iostream>
using namespace std;

//Node Structure
class Node
{
public:
  int data;
  Node *left,*right; 
  Node(int data,Node*left,Node*right)
  {
    this->data=data;
    this->left=left;
    this->right=right;
  }
};

class BST
{

public:
  Node*root;
  BST();

  Node* add_node(Node*,Node*,Node*,int);
  //public methods
  void add(int);
  void inorder(Node*,Node*,Node*);
};
BST::BST()
{
  root=NULL;
}

Node* BST :: add_node(Node*root,Node*left_node,Node*right_node,int data)
{

  if (root!=NULL )
  {
    if (root->data >= data)
    {
      if (root->left==left_node)
      {
        root->left = new Node(data,left_node,root);
      }
      else
      {
        root->left = add_node(root->left,left_node,root,data);
      }
    }
    else if (root->data < data)
    {
      if (root->right==right_node)
      {
        root->right = new Node(data,root,right_node);
      }
      else
      {
        root->right = add_node(root->right,root,right_node,data);
      }
    }
    return root;
  }
  else
  {
    return  new Node(data,left_node,right_node);
  }
}
//Adding a new node in binary search tree
void BST :: add(int data)
{

  root=add_node(root,NULL,NULL,data);
}

void BST :: inorder(Node*root,Node*left_node,Node*right_node)
{

  if (root!=NULL)
  {
    if (root->left!=left_node)
    {
      inorder(root->left,left_node,root);
    }  
    cout<<"  "<<root->data ;
    if (root->right != right_node)
    {
      inorder(root->right,root,right_node);
    }
  }

}

int main()
{
  //Create object
  BST obj;


  //Add nodes in binary search tree
  /*
         5
       /    \
      3      9
     / \     / \
    1   4   8   11
   / \     /      \
  -3  2   7        12


  */                


  obj.add(5); 
  obj.add(3); 
  obj.add(9); 
  obj.add(1); 
  obj.add(4); 
  obj.add(8); 
  obj.add(11); 
  obj.add(-3); 
  obj.add(2); 
  obj.add(7); 
  obj.add(12); 

  obj.inorder(obj.root,NULL,NULL);

  return 0;
}

Output

 -3  1  2  3  4  5  7  8  9  11  12
//Java program
//Implement Threaded Binary Search Tree
class Node
{
  public int data;
  public Node left,right;
  public Node(int data,Node left,Node right)
  {
    this.data=data;
    this.left=left;
    this.right=right;
  }
}
public class BST
{


  public Node root;
  //Class constructors
  BST()
  {
    root=null;
  } 

  Node add_node(Node root,Node left_node,Node right_node,int data)
  {

    if (root!=null )
    {
      if (root.data >= data)
      {
        if (root.left==left_node)
        {
          root.left = new Node(data,left_node,root);
        }
        else
        {
          root.left = add_node(root.left,left_node,root,data);
        }
      }
      else if (root.data < data)
      {
        if (root.right==right_node)
        {
          root.right = new Node(data,root,right_node);
        }
        else
        {
          root.right = add_node(root.right,root,right_node,data);
        }
      }
      return root;
    }
    else
    {
      return  new Node(data,left_node,right_node);
    }
  }
  //Adding a new node in binary search tree
  public void add(int data)
  {

    root=add_node(root,null,null,data);
  }

  public void   inorder(Node root,Node left_node,Node right_node)
  {

    if (root!=null)
    {
      if (root.left!=left_node)
      {
        inorder(root.left,left_node,root);
      }  
      System.out.print("  "+root.data) ;
      if (root.right != right_node)
      {
        inorder(root.right,root,right_node);
      }
    }

  }


  public static void main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /*
           5
         /    \
        3      9
       / \     / \
      1   4   8   11
     / \     /      \
    -3  2   7        12


    */                


    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 
    obj.add(7); 
    obj.add(12); 

    obj.inorder(obj.root,null,null);

  }
}

Output

  -3  1  2  3  4  5  7  8  9  11  12
internal node presentation in threaded BST
#Python Program 
#Implement Threaded Binary Search Tree
class Node:
  def __init__(self,data,left,right):
    self.data=data
    self.left=left
    self.right=right

   
class BST:

  def __init__(self):

    #Assign default value
    self.root=None
  

  def  add_node(self,root,left_node,right_node, data) :

    if (root!=None ) :

      if (root.data >= data) :

        if (root.left==left_node) :

          root.left =  Node(data,left_node,root)
        else :

          root.left = self.add_node(root.left,left_node,root,data)
      elif (root.data < data) :

        if (root.right==right_node) :

          root.right =  Node(data,root,right_node)
        else :

          root.right = self.add_node(root.right,root,right_node,data)
      return root
    else :

      return   Node(data,left_node,right_node)
  #Adding a new node in binary search tree
  def   add(self, data) :

    self.root=self.add_node(self.root,None,None,data)
  
  def  inorder(self,root,left_node,right_node) :

    if (root!=None) :

      if (root.left!=left_node) :

        self.inorder(root.left,left_node,root)
      
      print(root.data ,end="  ")

      if (root.right != right_node) :

        self.inorder(root.right,root,right_node)
def main():
  obj = BST()


  #Add nodes in binary search tree
  #
  #         5
  #       /    \
  #      3      9
  #     / \     / \
  #    1   4   8   11
  #   / \     /      \
  #  -3  2   7        12
  #  
  obj.add(5) 
  obj.add(3) 
  obj.add(9) 
  obj.add(1) 
  obj.add(4) 
  obj.add(8) 
  obj.add(11) 
  obj.add(-3) 
  obj.add(2) 
  obj.add(7) 
  obj.add(12) 
  obj.inorder(obj.root,None,None)
if __name__ =="__main__":
  main()

Output

-3  1  2  3  4  5  7  8  9  11  12 
//C# program
//Implement Threaded Binary Search Tree
using System;
public class Node
{
  public int data;
  public Node left,right;
  public Node(int data,Node left,Node right)
  {
    this.data=data;
    this.left=left;
    this.right=right;
  }
}
public class BST
{


  public Node root;
  //Class constructors
  BST()
  {
    root=null;
  } 

  Node add_node(Node root,Node left_node,Node right_node,int data)
  {

    if (root!=null )
    {
      if (root.data >= data)
      {
        if (root.left==left_node)
        {
          root.left = new Node(data,left_node,root);
        }
        else
        {
          root.left = add_node(root.left,left_node,root,data);
        }
      }
      else if (root.data < data)
      {
        if (root.right==right_node)
        {
          root.right = new Node(data,root,right_node);
        }
        else
        {
          root.right = add_node(root.right,root,right_node,data);
        }
      }
      return root;
    }
    else
    {
      return  new Node(data,left_node,right_node);
    }
  }
  //Adding a new node in binary search tree
  public void add(int data)
  {

    root=add_node(root,null,null,data);
  }

  public void   inorder(Node root,Node left_node,Node right_node)
  {

    if (root!=null)
    {
      if (root.left!=left_node)
      {
        inorder(root.left,left_node,root);
      }  
      Console.Write("  "+root.data) ;
      if (root.right != right_node)
      {
        inorder(root.right,root,right_node);
      }
    }

  }


  public static void Main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /*
           5
         /    \
        3      9
       / \     / \
      1   4   8   11
     / \     /      \
    -3  2   7        12


    */                


    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 
    obj.add(7); 
    obj.add(12); 

    obj.inorder(obj.root,null,null);

  }
}

Output

  -3  1  2  3  4  5  7  8  9  11  12
<?php
//Php program 
//Implement Threaded Binary Search Tree
class Node
{
  public $data;
  public $left;
  public $right;
  function __construct($data,$left,$right)
  {
    $this->data = $data;
    $this->left = $left;
    $this->right = $right;
  }
}
class BST
{

  public $root;

  function __construct()
  {
    $root=NULL;
  }
  public function add_node($root,$left_node,$right_node, $data)
  {

    if ($root!=NULL )
    {
      if ($root->data >= $data)
      {
        if ($root->left==$left_node)
        {
          $root->left = new Node($data,$left_node,$root);
        }
        else
        {
          $root->left = $this->add_node($root->left,$left_node,$root,$data);
        }
      }
      else if ($root->data < $data)
      {
        if ($root->right==$right_node)
        {
          $root->right = new Node($data,$root,$right_node);
        }
        else
        {
          $root->right = $this->add_node($root->right,$root,$right_node,$data);
        }
      }
      return $root;
    }
    else
    {
      return  new Node($data,$left_node,$right_node);
    }
  }
  //Adding a new node in binary search tree
  public function  add( $data)
  {

    $this->root=$this->add_node($this->root,NULL,NULL,$data);
  }

  public function inorder($root,$left_node,$right_node)
  {

    if ($root!=NULL)
    {
      if ($root->left!=$left_node)
      {
        $this->inorder($root->left,$left_node,$root);
      }  
      echo "  ".$root->data ;
      if ($root->right != $right_node)
      {
        $this->inorder($root->right,$root,$right_node);
      }
    }

  }
}
function main()
{
  //Make a object of BST class
  $obj= new BST();
//Add nodes in binary search tree
  /*
         5
       /    \
      3      9
     / \     / \
    1   4   8   11
   / \     /      \
  -3  2   7        12


  */                


  $obj->add(5); 
  $obj->add(3); 
  $obj->add(9); 
  $obj->add(1); 
  $obj->add(4); 
  $obj->add(8); 
  $obj->add(11); 
  $obj->add(-3); 
  $obj->add(2); 
  $obj->add(7); 
  $obj->add(12); 

  $obj->inorder($obj->root,NULL,NULL);

}
main();
?>

Output

  -3  1  2  3  4  5  7  8  9  11  12
# Ruby Program
# Threaded Binary Search Tree insertion

class Node 
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right
  def initialize(value, left_node, right_node) 
    self.data = value
    self.left = left_node
    self.right = right_node
  end
end

class BinarySearchTree 
  attr_reader :root
  attr_accessor :root
  def initialize() 
    @root = nil
  end
  def add_node(head, left_node, right_node, value) 
    if (head != nil) 
      if (head.data >= value) 
        if (head.left == left_node) 
          head.left = Node.new(value, left_node, head)
        else 
          head.left = self.add_node(head.left, left_node, head, value)
        end
      elsif (head.data < value) 
        if (head.right == right_node) 
          head.right = Node.new(value, head, right_node)
        else 
          head.right = self.add_node(head.right, head, right_node, value)
        end
      end
      return head
    else 
      return Node.new(value, left_node, right_node)
    end
  end
  def add(value) 
    @root = self.add_node(@root, nil, nil, value)
  end
  def inorder(head, left_node, right_node) 
    if (head != nil) 
      if (head.left != left_node) 
        self.inorder(head.left, left_node, head)
      end
      print("  ", head.data)
      if (head.right != right_node) 
        self.inorder(head.right, head, right_node)
      end
    end
  end
end
def main() 
  obj = BinarySearchTree.new()
  obj.add(5)
  obj.add(3)
  obj.add(9)
  obj.add(1)
  obj.add(4)
  obj.add(8)
  obj.add(11)
  obj.add(-3)
  obj.add(2)
  obj.add(7)
  obj.add(12)
  obj.inorder(obj.root, nil, nil)
end


main()

Output

  -3  1  2  3  4  5  7  8  9  11  12
/*
 Node Js Program
 Threaded Binary Search Tree insertion
*/

class Node {

  constructor(value, left_node, right_node) {
    this.data = value;
    this.left = left_node;
    this.right = right_node;
  }
}
class BinarySearchTree {
  
  constructor() {
    this.root = null;
  }
  add_node(head, left_node, right_node, value) {
    if (head != null) {
      if (head.data >= value) {
        if (head.left == left_node) {
          head.left = new Node(value, left_node, head);
        } else {
          head.left = this.add_node(head.left, left_node, head, value);
        }
      } else
      if (head.data < value) {
        if (head.right == right_node) {
          head.right = new Node(value, head, right_node);
        } else {
          head.right = this.add_node(head.right, head, right_node, value);
        }
      }
      return head;
    } else {
      return new Node(value, left_node, right_node);
    }
  }
  add(value) {
    this.root = this.add_node(this.root, null, null, value);
  }
  inorder(head, left_node, right_node) {
    if (head != null) {
      if (head.left != left_node) {
        this.inorder(head.left, left_node, head);
      }
      process.stdout.write("  " + head.data);
      if (head.right != right_node) {
        this.inorder(head.right, head, right_node);
      }
    }
  }
}

function main() {
  var obj = new BinarySearchTree();
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(8);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(7);
  obj.add(12);
  obj.inorder(obj.root, null, null);
}

main();

Output

  -3  1  2  3  4  5  7  8  9  11  12
/*
 Swift 4 Program
 Threaded Binary Search Tree insertion
*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int, _ left_node: Node? , _ right_node : Node? ) {
    self.data = value;
    self.left = left_node;
    self.right = right_node;
  }
}
class BinarySearchTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func add_node(_ head: Node? , _ left_node : Node? , _ right_node : Node? , _ value : Int)->Node? {
    if (head != nil) {
      if (head!.data >= value) {
        if (head!.left === left_node) {
          head!.left = Node(value, left_node, head);
        } else {
          head!.left = self.add_node(head!.left, left_node, head, value);
        }
      } else
      if (head!.data < value) {
        if (head!.right === right_node) {
          head!.right = Node(value, head, right_node);
        } else {
          head!.right = self.add_node(head!.right, head, right_node, value);
        }
      }
      return head;
    } else {
      return Node(value, left_node, right_node);
    }
  }
  func add(_ value: Int) {
    self.root = self.add_node(self.root, nil, nil, value);
  }
  func inorder(_ head: Node? , _ left_node : Node? , _ right_node : Node? ) {
    if (head != nil) {
      if (!(head!.left === left_node)) {
        self.inorder(head!.left, left_node, head);
      }
      print(" ", head!.data,terminator:"");
      if (!(head!.right === right_node)) {
        self.inorder(head!.right, head, right_node);
      }
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(8);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(7);
  obj.add(12);
  obj.inorder(obj.root, nil, nil);
}
main();

Output

  -3  1  2  3  4  5  7  8  9  11  12


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