Convert binary tree to threaded binary tree

Binary tree to threaded binary tree conversion

Here given code implementation process.

/*
  C Program 
+ Convert left-right representation of a binary tree to down-right
*/
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Tree node
struct Node
{
  int data;
  struct Node*left,*right;
};

//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes

struct Node* newNode(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;
  
}

void inorder(struct Node *root) 
{ 
  if (root != NULL) 
  { 
    
         
    inorder(root->left);
    printf("%3d",root->data);
    inorder(root->right);

  } 
} 
void threadedBT(struct Node *head, struct Node *leftP,struct Node *rightP) {
  if (head != NULL) {
    threadedBT(head->left, leftP, head);
    threadedBT(head->right, head, rightP);
    if (head->left == NULL) {
      head->left = leftP;
    }
    if (head->right == NULL) {
      head->right = rightP;
    }
  }
}
void threaded_inorder(struct Node *head, struct Node *leftP,struct Node *rightP) {
  if (head != NULL) {
    if(head->left != leftP )
    {
      threaded_inorder(head->left, leftP, head);
    }
    printf("%3d",head->data);
    
    if(head->right != rightP)
    {
      threaded_inorder(head->right, head, rightP);
    }

  }
}
int main(){

  struct Node*root=NULL;
    /*   Make A Binary Tree
    -----------------------
            1
           /  \
          2    3
         /    /  \
        4    5    6
         \
          7
         / 
        8
    */
  root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->right->right = newNode(6);
  root->right->left = newNode(5);
  root->left->left = newNode(4);
  root->left->left->right = newNode(7);
  root->left->left->right->left = newNode(8);
  inorder(root);
  threadedBT(root, NULL, NULL);

  printf("\n Threaded inorder \n");
  threaded_inorder(root, NULL, NULL);
  return 0;
}

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
/*
  C++ Program
  Convert binary tree to threaded binary tree
*/
#include <iostream>

using namespace std;
class Node {
  public:
    int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinaryTree {
  public:
    Node *root;
  BinaryTree() {
    this->root = NULL;
  }
  void inorder(Node *head) {
    if (head != NULL) {
      this->inorder(head->left);
      cout << "  " << head->data;
      this->inorder(head->right);
    }
  }
  //Convert Binary tree to Threaded Binary tree
  void threadedBT(Node *head, Node *leftP, Node *rightP) {
    if (head != NULL) {
      this->threadedBT(head->left, leftP, head);
      this->threadedBT(head->right, head, rightP);
      if (head->left == NULL) {
        head->left = leftP;
      }
      if (head->right == NULL) {
        head->right = rightP;
      }
    }
  }
  void threaded_inorder(Node *head, Node *leftP, Node *rightP) {
    if (head != NULL) {
      if (head->left != leftP) {
        threaded_inorder(head->left, leftP, head);
      }
      cout << "  " << head->data;

      if (head->right != rightP) {
        threaded_inorder(head->right, head, rightP);
      }

    }
  }
};

int main() {
  BinaryTree obj;
  /*   Make A Binary Tree
    -----------------------
            1
           /  \
          2    3
         /    /  \
        4    5    6
         \
          7
         / 
        8
  */
  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->left->left->right->left = new Node(8);
  obj.inorder(obj.root);
  obj.threadedBT(obj.root, NULL, NULL);

  cout << "\n Threaded inorder \n";
  obj.threaded_inorder(obj.root, NULL, NULL);
  return 0;
}

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
/* 
  Java Program 
  Convert binary tree to threaded binary tree
  //using recursion
 */

//Structure of Binary Tree node
class Node
{
 
    public int data;
    public Node left;
    public Node right;
    //make a tree node
    public Node(int value)
    {
      //Assign field values
      data=value;
      left=null;
      right=null;
    }
};

public class BinaryTree
{

  public Node root;

  public BinaryTree(){
    //Set initial tree root to null
    root=null;
  }
  //Display tree element inorder form
  public void inorder(Node head)
  {

    if(head!=null)
    {
      inorder(head.left);
      //Print node value
      System.out.print("  "+head.data);
      inorder(head.right);
    }

  }
  //Converting a given binary to its threaded binary tree
  public void threadedBT(Node head,Node leftP ,Node rightP)
  {
    if(head != null)
    {
      threadedBT(head.left,leftP,head);
  
      threadedBT(head.right,head,rightP);
   
      if(head.left == null)
      {
        head.left=leftP;
      }
      if(head.right == null)
      {
        head.right = rightP;
      }
    }
  }
  public void threaded_inorder(Node head,Node leftP ,Node rightP)
  {
    if(head != null)
    {
      
      if(head.left != leftP)
      {
        threaded_inorder(head.left,leftP,head);
      }
      System.out.print("  "+head.data);
      if(head.right != rightP)
      {
        threaded_inorder(head.right,head,rightP);
      }
    }
  }
  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
    */
    //Add binary tree elements
    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.left.left.right.left = new Node(8);
    //Display Tree elements
    obj.inorder(obj.root);

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

    System.out.print("\n Threaded Inorder  \n");
    obj.threaded_inorder(obj.root,null,null);
  }
}

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
/* 
  C# Program 
  Convert binary tree to threaded binary tree
  //using recursion
 */
using System;
//Structure of Binary Tree node
public class Node
{

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

public class BinaryTree
{

	public Node root;

	public BinaryTree(){
		//Set initial tree root to null
		root=null;
	}
	//Display tree element inorder form
	public void inorder(Node head)
	{

		if(head!=null)
		{
			inorder(head.left);
			//Print node value
			Console.Write("  "+head.data);
			inorder(head.right);
		}

	}
	//Converting a given binary to its threaded binary tree
	public void threadedBT(Node head,Node leftP ,Node rightP)
	{
		if(head != null)
		{
			threadedBT(head.left,leftP,head);

			threadedBT(head.right,head,rightP);

			if(head.left == null)
			{
				head.left=leftP;
			}
			if(head.right == null)
			{
				head.right = rightP;
			}
		}
	}
	public void threaded_inorder(Node head,Node leftP ,Node rightP)
	{
		if(head != null)
		{

			if(head.left != leftP)
			{
				threaded_inorder(head.left,leftP,head);
			}
			Console.Write("  "+head.data);
			if(head.right != rightP)
			{
				threaded_inorder(head.right,head,rightP);
			}
		}
	}
	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
    */
		//Add binary tree elements
		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.left.left.right.left = new Node(8);
		//Display Tree elements
		obj.inorder(obj.root);

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

		Console.Write("\n Threaded Inorder  \n");
		obj.threaded_inorder(obj.root,null,null);
	}
}

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
# Python Program 
# Convert binary tree to threaded binary tree
class Node :

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

class BinaryTree :

  def __init__(self) :
    self.root = None
  
  def inorder(self, head) :
    if (head != None) :
      self.inorder(head.left)
      print(head.data,end="  ")
      self.inorder(head.right)
    
  
  def threadedBT(self, head, leftP, rightP) :
    if (head != None) :
      self.threadedBT(head.left, leftP, head)
      self.threadedBT(head.right, head, rightP)
      if (head.left == None) :
        head.left = leftP
      
      if (head.right == None) :
        head.right = rightP
      
    
  
  def threaded_inorder(self, head, leftP, rightP) :
    if (head != None) :
      if (head.left != leftP) :
        self.threaded_inorder(head.left, leftP, head)
      
      print(head.data,end="  ")
      if (head.right != rightP) :
        self.threaded_inorder(head.right, head, rightP)
      
    
  
def main() :
  obj = BinaryTree()
  #   Make A Binary Tree
  #          1
  #         /  \
  #        2    3
  #       /    /  \
  #      4    5    6
  #       \
  #        7
  #       /
  #      8
  #  
  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.left.left.right.left = Node(8)
  obj.inorder(obj.root)
  obj.threadedBT(obj.root, None, None)
  print("\n Threaded Inorder  ")
  obj.threaded_inorder(obj.root, None, None)


if __name__ == "__main__":
  main()

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
# Ruby Program
# Convert binary tree to threaded binary tree
class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinaryTree 
	attr_reader :root
	attr_accessor :root
	def initialize() 
		@root = nil
	end
	def inorder(head) 
		if (head != nil) 
			self.inorder(head.left)
			print("  ", head.data)
			self.inorder(head.right)
		end
	end
	def threadedBT(head, leftP, rightP) 
		if (head != nil) 
			self.threadedBT(head.left, leftP, head)
			self.threadedBT(head.right, head, rightP)
			if (head.left == nil) 
				head.left = leftP
			end
			if (head.right == nil) 
				head.right = rightP
			end
		end
	end
	def threaded_inorder(head, leftP, rightP) 
		if (head != nil) 
			if (head.left != leftP) 
				self.threaded_inorder(head.left, leftP, head)
			end
			print("  ", head.data)
			if (head.right != rightP) 
				self.threaded_inorder(head.right, head, rightP)
			end
		end
	end
end
def main() 
	obj = BinaryTree.new()
	#   Make A Binary Tree
	#          1
	#         /  \
	#        2    3
	#       /    /  \
	#      4    5    6
	#       \
	#        7
	#       /
	#      8
	#  
	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.left.left.right.left = Node.new(8)
	obj.inorder(obj.root)
	obj.threadedBT(obj.root, nil, nil)
	print("\n Threaded Inorder  \n")
	obj.threaded_inorder(obj.root, nil, nil)
end


main()

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
<?php
/*
  Php Program
  Convert binary tree to threaded binary tree
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinaryTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function inorder($head) {
    if ($head != null) {
      $this->inorder($head->left);
      echo("  ". $head->data);
      $this->inorder($head->right);
    }
  }
  public  function threadedBT($head, $leftP, $rightP) {
    if ($head != null) {
      $this->threadedBT($head->left, $leftP, $head);
      $this->threadedBT($head->right, $head, $rightP);
      if ($head->left == null) {
        $head->left = $leftP;
      }
      if ($head->right == null) {
        $head->right = $rightP;
      }
    }
  }
  public  function threaded_inorder($head, $leftP, $rightP) {
    if ($head != null) {
      if ($head->left != $leftP) {
        $this->threaded_inorder($head->left, $leftP, $head);
      }
      echo("  ". $head->data);
      if ($head->right != $rightP) {
        $this->threaded_inorder($head->right, $head, $rightP);
      }
    }
  }
}
function main() {
  $obj = new BinaryTree();
  /*   Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \
        7
       / 
      8
  */
  $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->left->left->right->left = new Node(8);
  $obj->inorder($obj->root);
  $obj->threadedBT($obj->root, null, null);
  echo("\n Threaded Inorder  \n");
  $obj->threaded_inorder($obj->root, null, null);
}
main();

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
/*
  Node JS Program
  Convert binary tree to threaded binary tree
*/
class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree {
	
	constructor() {
		this.root = null;
	}
	inorder(head) {
		if (head != null) {
			this.inorder(head.left);
			process.stdout.write("  " + head.data);
			this.inorder(head.right);
		}
	}
	threadedBT(head, leftP, rightP) {
		if (head != null) {
			this.threadedBT(head.left, leftP, head);
			this.threadedBT(head.right, head, rightP);
			if (head.left == null) {
				head.left = leftP;
			}
			if (head.right == null) {
				head.right = rightP;
			}
		}
	}
	threaded_inorder(head, leftP, rightP) {
		if (head != null) {
			if (head.left != leftP) {
				this.threaded_inorder(head.left, leftP, head);
			}
			process.stdout.write("  " + head.data);
			if (head.right != rightP) {
				this.threaded_inorder(head.right, head, rightP);
			}
		}
	}
}

function main() {
	var obj = new BinaryTree();
	/*   Make A Binary Tree
    -----------------------
            1
           /  \
          2    3
         /    /  \
        4    5    6
         \
          7
         / 
        8
    */
	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.left.left.right.left = new Node(8);
	obj.inorder(obj.root);
	obj.threadedBT(obj.root, null, null);
	process.stdout.write("\n Threaded Inorder  \n");
	obj.threaded_inorder(obj.root, null, null);
}
main();

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6
/*
  Swift 4 Program
  Convert binary tree to threaded 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 BinaryTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print(head!.data, terminator: "  ");
      self.inorder(head!.right);
    }
  }
  func threadedBT(_ head: Node? , _ leftP : Node? , _ rightP : Node? ) {
    if (head != nil) {
      self.threadedBT(head!.left, leftP, head);
      self.threadedBT(head!.right, head, rightP);
      if (head!.left == nil) {
        head!.left = leftP;
      }
      if (head!.right == nil) {
        head!.right = rightP;
      }
    }
  }
  func threaded_inorder(_ head: Node? , _ leftP : Node? , _ rightP : Node? ) {
    if (head != nil) {
      if (!(head!.left===leftP)) {
        self.threaded_inorder(head!.left, leftP, head);
      }
      print(head!.data, terminator: "  ");
      if (!(head!.right===rightP)) {
        self.threaded_inorder(head!.right, head, rightP);
      }
    }
  }
}
func main() {
  let obj: BinaryTree = BinaryTree();
  /*   Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \
        7
       / 
      8
  */
  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!.left!.left!.right!.left = Node(8);
  obj.inorder(obj.root);
  obj.threadedBT(obj.root, nil, nil);
  print("\n Threaded Inorder ");
  obj.threaded_inorder(obj.root, nil, nil);
}
main();

Output

  4  8  7  2  1  5  3  6
 Threaded inorder 
  4  8  7  2  1  5  3  6


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