Skip to main content

Construct Binary Tree from a Linked List

Constructing a binary tree from a linked list means creating a binary tree structure from the data stored in a linked list. In a linked list, each node stores a data value and a reference to the next node in the list. On the other hand, a binary tree is a tree data structure where each node can have at most two children, referred to as the left child and the right child.

Construct Binary Tree using Linked List

To construct a binary tree from a linked list, we can use the values in the linked list to create the nodes of the binary tree. Each node in the binary tree will have a left child and a right child, which can be recursively constructed using the remaining elements of the linked list.

One common approach to construct a binary tree from a linked list is to use a queue data structure. We can initially push the head node of the linked list onto the queue. Then, we can dequeue a node from the queue and create a new binary tree node with its value. We can then enqueue the left child and right child of the new node by taking the next two nodes from the linked list. We repeat this process until we have processed all nodes in the linked list. At the end, the binary tree will have been constructed from the linked list.

Program Solution

//C Program
//Construct Binary Tree from a Linked List 
#include <stdio.h>

#include <stdlib.h> //for malloc function

//Create structure of BT
struct Node {
  int data;
  struct Node *next;
};

//Structure of Binary Tree node
struct Tree {
  int data;
  struct Tree *left, *right;
};
struct Queue {
  struct Tree *element;
  struct Queue *next;
};


//insert Node into linked list
void insert(struct Node **head, int value) {
  //Create dynamic node
  struct Node *node = (struct Node *) malloc(sizeof(struct Node));
  if (node == NULL) {
    printf("Memory overflow\n");
  } else {
    node->data = value;
    node->next = NULL;
    if ( *head == NULL) {
      *head = node;
    } else {
      struct Node *temp = *head;
      //find last node
      while (temp->next != NULL) {
        temp = temp->next;
      }
      //add node at last possition
      temp->next = node;
    }
  }
}
//return a new node of binary tree
struct Tree *addNode(int data) {
  //create dynamic memory to new binary tree node
  struct Tree *new_node = (struct Tree *) malloc(sizeof(struct Tree));
  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 Queue element and return this reference
struct Queue *enqueue(struct Tree *tree_node) {

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

  } else {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  return Queue_node;
}
//Remove Queue elements
void dequeue(struct Queue **front) {
  if ( *front != NULL) {
    struct Queue *remove = *front;
    *front = remove->next;
    remove->element = NULL;
    remove->next = NULL;
    free(remove);
    remove = NULL;

  }
}
//This method are construct binary tree
struct Tree *construct(struct Node *head) {
  if (head == NULL) 
  {
    return NULL;
  }

  //create first node node binary tree
  struct Tree *root = addNode(head->data), *new_node = NULL;

  //This two pointer are manage insertion in binary tree
  //
  struct Queue *front = NULL, *back = NULL;

  //add first node of queue
  front = back = enqueue(root);

  head = head->next;

  while (head != NULL) {
    //Left child
    new_node = addNode(head->data);
    front->element->left = new_node;
    back->next = enqueue(new_node);
    back = back->next;

    if (head->next != NULL) {
      //add right child node
      new_node = addNode(head->next->data);
      front->element->right = new_node;
      back->next = enqueue(new_node);
      back = back->next;
      head = head->next;
    }
    head = head->next;
    //remove a first node of queue element
    dequeue( &front);
  }
  //final return root node of tree
  return root;
}
//Display tree element preorder form
void preOrderData(struct Tree *node) {

  if (node != NULL) {
    //Print node value
    printf("%3d", node->data);
    preOrderData(node->left);

    preOrderData(node->right);
  }
}

//Display tree element In OrderData form
void inOrderData(struct Tree *node) {

  if (node != NULL) {

    inOrderData(node->left);
    //Print node value
    printf("%3d", node->data);
    inOrderData(node->right);
  }
}

//Display tree element In Post order form
void postOrderData(struct Tree *node) {

  if (node != NULL) {

    postOrderData(node->left);

    postOrderData(node->right);

    //Print node value
    printf("%3d", node->data);
  }
}
int main() {
  //create node pointer
  struct Node *head = NULL;
  //insert element of linked list
  insert( &head, 1);
  insert( &head, 2);
  insert( &head, 3);
  insert( &head, 4);
  insert( &head, 5);
  insert( &head, 6);
  insert( &head, 7);
  insert( &head, 8);
  /*
           1
         /   \
        2     3
       / \   / \
      4   5 6   7
     /
    8   
  */
  struct Tree *root = construct(head);

  //Display elements
  printf("Preorder :\n");
  preOrderData(root);

  printf("\nInorder :\n");
  inOrderData(root);

  printf("\nPostorder :\n");
  postOrderData(root);
  return 0;
}

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
/*
C++ Program 
Construct Binary Tree from a Linked List 
*/
#include<iostream>

using namespace std;
class TreeNode {
public:
  int data;
  TreeNode *left, *right;
  TreeNode(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class LinkNode {
  public:
  int data;
  LinkNode *next;
  LinkNode(int value) {
    this->data = value;
    this->next = NULL;
  }
};
class MyQueue {
  public:
  TreeNode *element;
  MyQueue *next;
  MyQueue(TreeNode *node) {
    this->element = node;
    this->next = NULL;
  }
};
class BinaryTree {
  public:
  TreeNode *root;
  LinkNode *head;
  MyQueue *front, *back;
  BinaryTree() {
    this->root = NULL;
    this->head = NULL;
    this->front = NULL;
    this->back = NULL;
  }
  void insert(int value) {
    LinkNode *node = new LinkNode(value);
    if (node == NULL) {
      cout << "Memory overflow\n";
    } else {
      if (this->head == NULL) {
        this->head = node;
      } else {
        LinkNode *temp = this->head;
        while (temp->next != NULL) {
          temp = temp->next;
        }
        temp->next = node;
      }
    }
  }
  void in_order(TreeNode *node) {
    if (node != NULL) {
      this->in_order(node->left);
      cout << "  " << node->data;
      this->in_order(node->right);
    }
  }
  void pre_order(TreeNode *node) {
    if (node != NULL) {
       cout << "  " << node->data;
      this->pre_order(node->left);
      this->pre_order(node->right);
    }
  }
  void post_order(TreeNode *node) {
    if (node != NULL) {
      this->post_order(node->left);
      this->post_order(node->right);
      cout << "  " << node->data;
    }
  }
  MyQueue *enqueue(TreeNode *tree_node) {
    return new MyQueue(tree_node);
  }
  void dequeue() {
    if (this->front != NULL) {
      MyQueue *remove = this->front;
      this->front = remove->next;
      remove->element = NULL;
      remove->next = NULL;
      remove = NULL;
    }
  }
  void construct() {
    if (this->head == NULL) {
      return;
    }
    this->root = new TreeNode(this->head->data);
    TreeNode *new_node = NULL;
    this->front = this->back = this->enqueue(this->root);
    this->head = this->head->next;
    while (this->head != NULL) {
      new_node = new TreeNode(this->head->data);
      this->front->element->left = new_node;
      this->back->next = this->enqueue(new_node);
      this->back = this->back->next;
      if (this->head->next != NULL) {
        new_node = new TreeNode(this->head->next->data);
        this->front->element->right = new_node;
        this->back->next = this->enqueue(new_node);
        this->back = this->back->next;
        this->head = this->head->next;
      }
      this->head = this->head->next;
      this->dequeue();
    }
  }
};

int main() {
  BinaryTree obj;
  /*
           1
         /   \
        2     3
       / \   / \
      4   5 6   7
     /
    8   
  */
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  obj.insert(7);
  obj.insert(8);
  obj.construct();
  cout << "\nIn-order Data : \n";
  obj.in_order(obj.root);
  cout << "\nPre-order Data : \n";
  obj.pre_order(obj.root);
  cout << "\nPost-order Data : \n";
  obj.post_order(obj.root);
  return 0;
}

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
/*
Java Program 
Construct Binary Tree from a Linked List 
*/

//Class of Binary Tree Node
class TreeNode {

  public int data;

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


//Class of Linked List Node
class LinkNode {

  public int data;
  public LinkNode next;
  //Make a tree TreeNode
  public LinkNode(int value) {
    //Assign field values
    data = value;
    next = null;
  }
}


//Class of Linked List Node
class MyQueue {

  public TreeNode element;
  public MyQueue next;
  //Make a tree TreeNode
  public MyQueue(TreeNode node) {
    //Assign field values
    element = node;
    next = null;
  }
}


public class BinaryTree {

  public TreeNode root;
  public LinkNode head;
  public MyQueue front, back;

  public BinaryTree() {
    //Set initial values
    root = null;
    head = null;
    front = null;
    back = null;
  }
  //insert Node into linked list
  public void insert(int value) {
    //Create dynamic node
    LinkNode node = new LinkNode(value);
    if (node == null) {
      System.out.print("Memory overflow\n");
    } else {
      if (this.head == null) {
        this.head = node;
      } else {
        LinkNode temp = this.head;
        //find last node
        while (temp.next != null) {
          temp = temp.next;
        }
        //add node at last possition
        temp.next = node;
      }
    }
  }

  //Display tree element inorder form
  public void in_order(TreeNode node) {

    if (node != null) {

      in_order(node.left);
      //Print TreeNode value
      System.out.print("  " + node.data);
      in_order(node.right);
    }
  }
  //Display tree element preorder form
  public void pre_order(TreeNode node) {

    if (node != null) {
      //Print TreeNode value
      System.out.print("  " + node.data);
      pre_order(node.left);

      pre_order(node.right);
    }
  }
  //Display tree element preorder form
  public void post_order(TreeNode node) {

    if (node != null) {

      post_order(node.left);

      post_order(node.right);
      //Print TreeNode value
      System.out.print("  " + node.data);
    }
  }

  //Create a Queue element and return this reference
  public MyQueue enqueue(TreeNode tree_node) {

    return new MyQueue(tree_node);

  }
  //Remove Queue elements
  public void dequeue() {
    if (this.front != null) {
      MyQueue remove = this.front;
      this.front = remove.next;
      remove.element = null;
      remove.next = null;

      remove = null;
    }
  }
  //This method are construct binary tree
  public void construct() {
    if (this.head == null) {
      return;
    }

    //create first node node binary tree
    this.root = new TreeNode(head.data);
    TreeNode new_node = null;


    //add first node of queue
    this.front = this.back = enqueue(this.root);

    this.head = this.head.next;

    while (this.head != null) {
      //Left child
      new_node = new TreeNode(this.head.data);
      this.front.element.left = new_node;
      this.back.next = enqueue(new_node);
      this.back = this.back.next;

      if (this.head.next != null) {
        //add right child node
        new_node = new TreeNode(this.head.next.data);
        this.front.element.right = new_node;
        this.back.next = enqueue(new_node);
        this.back = this.back.next;
        this.head = this.head.next;
      }
      this.head = this.head.next;
      //remove a first node of queue element
      dequeue();
    }

  }


  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();


    //insert element of linked list
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);

    /*
             1
           /   \
          2     3
         / \   / \
        4   5 6   7
       /
      8   
    */

    obj.construct();


    System.out.print("\nIn-order Data : \n");
    obj.in_order(obj.root);

    System.out.print("\nPre-order Data : \n");
    obj.pre_order(obj.root);

    System.out.print("\nPost-order Data : \n");
    obj.post_order(obj.root);

  }
}

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
/*
C# Program 
Construct Binary Tree from a Linked List 
*/
using System;
//Class of Binary Tree Node
public class TreeNode {

	public int data;

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


//Class of Linked List Node
public class LinkNode {

	public int data;
	public LinkNode next;
	//Make a tree TreeNode
	public LinkNode(int value) {
		//Assign field values
		data = value;
		next = null;
	}
}


//Class of Linked List Node
public class MyQueue {

	public TreeNode element;
	public MyQueue next;
	//Make a tree TreeNode
	public MyQueue(TreeNode node) {
		//Assign field values
		element = node;
		next = null;
	}
}


public class BinaryTree {

	public TreeNode root;
	public LinkNode head;
	public MyQueue front, back;

	public BinaryTree() {
		//Set initial values
		root = null;
		head = null;
		front = null;
		back = null;
	}
	//insert Node into linked list
	public void insert(int value) {
		//Create dynamic node
		LinkNode node = new LinkNode(value);
		if (node == null) {
			Console.Write("Memory overflow\n");
		} else {
			if (this.head == null) {
				this.head = node;
			} else {
				LinkNode temp = this.head;
				//find last node
				while (temp.next != null) {
					temp = temp.next;
				}
				//add node at last possition
				temp.next = node;
			}
		}
	}

	//Display tree element inorder form
	public void in_order(TreeNode head) {

		if (head != null) {

			in_order(head.left);
			//Print TreeNode value
			Console.Write("  " + head.data);
			in_order(head.right);
		}
	}
	//Display tree element preorder form
	public void pre_order(TreeNode head) {

		if (head != null) {
			//Print TreeNode value
			Console.Write("  " + head.data);
			pre_order(head.left);

			pre_order(head.right);
		}
	}
	//Display tree element preorder form
	public void post_order(TreeNode head) {

		if (head != null) {

			post_order(head.left);

			post_order(head.right);
			//Print TreeNode value
			Console.Write("  " + head.data);
		}
	}

	//Create a Queue element and return this reference
	public MyQueue enqueue(TreeNode tree_node) {

		return new MyQueue(tree_node);

	}
	//Remove Queue elements
	public void dequeue() {
		if (this.front != null) {
			MyQueue remove = this.front;
			this.front = remove.next;
			remove.element = null;
			remove.next = null;

			remove = null;
		}
	}
	//This method are construct binary tree
	public void construct() {
		if (this.head == null) {
			return;
		}

		//create first node node binary tree
		this.root = new TreeNode(head.data);
		TreeNode new_node = null;


		//add first node of queue
		this.front = this.back = enqueue(this.root);

		this.head = this.head.next;

		while (this.head != null) {
			//Left child
			new_node = new TreeNode(this.head.data);
			this.front.element.left = new_node;
			this.back.next = enqueue(new_node);
			this.back = this.back.next;

			if (this.head.next != null) {
				//add right child node
				new_node = new TreeNode(this.head.next.data);
				this.front.element.right = new_node;
				this.back.next = enqueue(new_node);
				this.back = this.back.next;
				this.head = this.head.next;
			}
			this.head = this.head.next;
			//remove a first node of queue element
			dequeue();
		}

	}


	public static void Main(String[] args) {
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();


		//insert element of linked list
		obj.insert(1);
		obj.insert(2);
		obj.insert(3);
		obj.insert(4);
		obj.insert(5);
		obj.insert(6);
		obj.insert(7);
		obj.insert(8);

		/*
             1
           /   \
          2     3
         / \   / \
        4   5 6   7
       /
      8   
    */

		obj.construct();


		Console.Write("\nIn-order Data : \n");
		obj.in_order(obj.root);

		Console.Write("\nPre-order Data : \n");
		obj.pre_order(obj.root);

		Console.Write("\nPost-order Data : \n");
		obj.post_order(obj.root);

	}
}

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
# Python Program 
# Construct Binary Tree from a Linked List 
class TreeNode :

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

class LinkNode :
 
  def __init__(self, value) :
    self.data = value
    self.next = None
  

class MyQueue :

  def __init__(self, node) :
    self.element = node
    self.next = None
  

class BinaryTree :

  def __init__(self) :
    self.root = None
    self.head = None
    self.front = None
    self.back = None
  
  def insert(self, value) :
    node = LinkNode(value)
    if (node == None) :
      print("Memory overflow\n")
    else :
      if (self.head == None) :
        self.head = node
      else :
        temp = self.head
        while (temp.next != None) :
          temp = temp.next
        
        temp.next = node
      
    
  
  def in_order(self, node) :
    if (node != None) :
      self.in_order(node.left)
      print(node.data,end="  ")
      self.in_order(node.right)
    
  
  def pre_order(self, node) :
    if (node != None) :
      print(node.data,end="  ")
      self.pre_order(node.left)
      self.pre_order(node.right)
    
  
  def post_order(self, node) :
    if (node != None) :
      self.post_order(node.left)
      self.post_order(node.right)
      print(node.data,end="  ")
    
  
  def enqueue(self, tree_node) :
    return MyQueue(tree_node)
  
  def dequeue(self) :
    if (self.front != None) :
      remove = self.front
      self.front = remove.next
      remove.element = None
      remove.next = None
      remove = None
    
  
  def construct(self) :
    if (self.head == None) :
      return
    
    self.root = TreeNode(self.head.data)
    new_node = None
    self.front = self.back = self.enqueue(self.root)
    self.head = self.head.next
    while (self.head != None) :
      new_node = TreeNode(self.head.data)
      self.front.element.left = new_node
      self.back.next = self.enqueue(new_node)
      self.back = self.back.next
      if (self.head.next != None) :
        new_node = TreeNode(self.head.next.data)
        self.front.element.right = new_node
        self.back.next = self.enqueue(new_node)
        self.back = self.back.next
        self.head = self.head.next
      
      self.head = self.head.next
      self.dequeue()
    
  
def main() :
  obj = BinaryTree()
  
  #
  #           1
  #         /   \
  #        2     3
  #       / \   / \
  #      4   5 6   7
  #     /
  #    8
  #  
  obj.insert(1)
  obj.insert(2)
  obj.insert(3)
  obj.insert(4)
  obj.insert(5)
  obj.insert(6)
  obj.insert(7)
  obj.insert(8)
  obj.construct()
  print("\nIn-order Data : ")
  obj.in_order(obj.root)
  print("\nPre-order Data : ")
  obj.pre_order(obj.root)
  print("\nPost-order Data : ")
  obj.post_order(obj.root)
  

if __name__ == "__main__":
  main()

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
# Ruby Program
# Construct Binary Tree from a Linked List 
class TreeNode 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class LinkNode 
	attr_reader :data, :next
	attr_accessor :data, :next
	def initialize(value) 
		@data = value
		@next = nil
	end
end

class MyQueue 
	attr_reader :element, :next
	attr_accessor :element, :next
	def initialize(node) 
		@element = node
		@next = nil
	end
end

class BinaryTree 
	attr_reader :root, :head, :front, :back
	attr_accessor :root, :head, :front, :back
	def initialize() 
		@root = nil
		@head = nil
		@front = nil
		@back = nil
	end
	def insert(value) 
		node = LinkNode.new(value)
		if (node == nil) 
			print("Memory overflow\n")
		else 
			if (self.head == nil) 
				self.head = node
			else 
				temp = self.head
				while (temp.next != nil) 
					temp = temp.next
				end
				temp.next = node
			end
		end
	end
	def in_order(node) 
		if (node != nil) 
			self.in_order(node.left)
			print("  ", node.data)
			self.in_order(node.right)
		end
	end
	def pre_order(node) 
		if (node != nil) 
			print("  ", node.data)
			self.pre_order(node.left)
			self.pre_order(node.right)
		end
	end
	def post_order(node) 
		if (node != nil) 
			self.post_order(node.left)
			self.post_order(node.right)
			print("  ", node.data)
		end
	end
	def enqueue(tree_node) 
		return MyQueue.new(tree_node)
	end
	def dequeue() 
		if (self.front != nil) 
			remove = self.front
			self.front = remove.next
			remove.element = nil
			remove.next = nil
			remove = nil
		end
	end
	def construct() 
		if (self.head == nil) 
			return
		end
		self.root = TreeNode.new(@head.data)
		new_node = nil
		self.front = self.back = self.enqueue(self.root)
		self.head = self.head.next
		while (self.head != nil) 
			new_node = TreeNode.new(self.head.data)
			self.front.element.left = new_node
			self.back.next = self.enqueue(new_node)
			self.back = self.back.next
			if (self.head.next != nil) 
				new_node = TreeNode.new(self.head.next.data)
				self.front.element.right = new_node
				self.back.next = self.enqueue(new_node)
				self.back = self.back.next
				self.head = self.head.next
			end
			self.head = self.head.next
			self.dequeue()
		end
	end
end




def main() 
	obj = BinaryTree.new()


	#
	#           1
	#         /   \
	#        2     3
	#       / \   / \
	#      4   5 6   7
	#     /
	#    8
	#  
	obj.insert(1)
	obj.insert(2)
	obj.insert(3)
	obj.insert(4)
	obj.insert(5)
	obj.insert(6)
	obj.insert(7)
	obj.insert(8)
	obj.construct()
	print("\nIn-order Data  :\n")
	obj.in_order(obj.root)
	print("\nPre-order Data  :\n")
	obj.pre_order(obj.root)
	print("\nPost-order Data  :\n")
	obj.post_order(obj.root)
end

main()

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
<?php
/*
  Php Program
  Construct Binary Tree from a Linked List 
*/
class TreeNode {
  public $data;
  public $left;
  public $right;

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

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

  function __construct($node) {
    $this->element = $node;
    $this->next = null;
  }
}
class BinaryTree {
  public $root;
  public $head;
  public $front;
  public $back;

  function __construct() {
    $this->root = null;
    $this->head = null;
    $this->front = null;
    $this->back = null;
  }
  public  function insert($value) {
    $node = new LinkNode($value);
    if ($node == null) {
      echo("Memory overflow\n");
    } else {
      if ($this->head == null) {
        $this->head = $node;
      } else {
        $temp = $this->head;
        while ($temp->next != null) {
          $temp = $temp->next;
        }
        $temp->next = $node;
      }
    }
  }
  public  function in_order($node) {
    if ($node != null) {
      $this->in_order($node->left);
      echo("  ". $node->data);
      $this->in_order($node->right);
    }
  }
  public  function pre_order($node) {
    if ($node != null) {
      echo("  ". $node->data);
      $this->pre_order($node->left);
      $this->pre_order($node->right);
    }
  }
  public  function post_order($node) {
    if ($node != null) {
      $this->post_order($node->left);
      $this->post_order($node->right);
      echo("  ". $node->data);
    }
  }
  public  function enqueue($tree_node) {
    return new MyQueue($tree_node);
  }
  public  function dequeue() {
    if ($this->front != null) {
      $remove = $this->front;
      $this->front = $remove->next;
      $remove->element = null;
      $remove->next = null;
      $remove = null;
    }
  }
  public  function construct() {
    if ($this->head == null) {
      return;
    }
    $this->root = new TreeNode($this->head->data);
    $new_node = null;
    $this->front = $this->back = $this->enqueue($this->root);
    $this->head = $this->head->next;
    while ($this->head != null) {
      $new_node = new TreeNode($this->head->data);
      $this->front->element->left = $new_node;
      $this->back->next = $this->enqueue($new_node);
      $this->back = $this->back->next;
      if ($this->head->next != null) {
        $new_node = new TreeNode($this->head->next->data);
        $this->front->element->right = $new_node;
        $this->back->next = $this->enqueue($new_node);
        $this->back = $this->back->next;
        $this->head = $this->head->next;
      }
      $this->head = $this->head->next;
      $this->dequeue();
    }
  }

}
function main() {
  $obj = new BinaryTree();
  /*
           1
         /   \
        2     3
       / \   / \
      4   5 6   7
     /
    8   
  */
  $obj->insert(1);
  $obj->insert(2);
  $obj->insert(3);
  $obj->insert(4);
  $obj->insert(5);
  $obj->insert(6);
  $obj->insert(7);
  $obj->insert(8);
  $obj->construct();
  echo("\nIn-order Data : \n");
  $obj->in_order($obj->root);
  echo("\nPre-order Data : \n");
  $obj->pre_order($obj->root);
  echo("\nPost-order Data : \n");
  $obj->post_order($obj->root);
}
main();

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
/*
  Node JS Program
  Construct Binary Tree from a Linked List 
*/
class TreeNode {
	
	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class LinkNode {
	
	constructor(value) {
		this.data = value;
		this.next = null;
	}
}
class MyQueue {
	
	constructor(node) {
		this.element = node;
		this.next = null;
	}
}
class BinaryTree {

	constructor() {
		this.root = null;
		this.head = null;
		this.front = null;
		this.back = null;
	}
	insert(value) {
		var node = new LinkNode(value);
		if (node == null) {
			process.stdout.write("Memory overflow\n");
		} else {
			if (this.head == null) {
				this.head = node;
			} else {
				var temp = this.head;
				while (temp.next != null) {
					temp = temp.next;
				}
				temp.next = node;
			}
		}
	}
	in_order(node) {
		if (node != null) {
			this.in_order(node.left);
			process.stdout.write("  " + node.data);
			this.in_order(node.right);
		}
	}
	pre_order(node) {
		if (node != null) {
			process.stdout.write("  " + node.data);
			this.pre_order(node.left);
			this.pre_order(node.right);
		}
	}
	post_order(node) {
		if (node != null) {
			this.post_order(node.left);
			this.post_order(node.right);
			process.stdout.write("  " + node.data);
		}
	}
	enqueue(tree_node) {
		return new MyQueue(tree_node);
	}
	dequeue() {
		if (this.front != null) {
			var remove = this.front;
			this.front = remove.next;
			remove.element = null;
			remove.next = null;
			remove = null;
		}
	}
	construct() {
		if (this.head == null) {
			return;
		}
		this.root = new TreeNode(this.head.data);
		var new_node = null;
		this.front = this.back = this.enqueue(this.root);
		this.head = this.head.next;
		while (this.head != null) {
			new_node = new TreeNode(this.head.data);
			this.front.element.left = new_node;
			this.back.next = this.enqueue(new_node);
			this.back = this.back.next;
			if (this.head.next != null) {
				new_node = new TreeNode(this.head.next.data);
				this.front.element.right = new_node;
				this.back.next = this.enqueue(new_node);
				this.back = this.back.next;
				this.head = this.head.next;
			}
			this.head = this.head.next;
			this.dequeue();
		}
	}

}
function main() {
	var obj = new BinaryTree();
	/*
	       1
	     /   \
	    2     3
	   / \   / \
	  4   5 6   7
	 /
	8   
	*/
	obj.insert(1);
	obj.insert(2);
	obj.insert(3);
	obj.insert(4);
	obj.insert(5);
	obj.insert(6);
	obj.insert(7);
	obj.insert(8);
	obj.construct();
	process.stdout.write("\nIn-order Data : \n");
	obj.in_order(obj.root);
	process.stdout.write("\nPre-order Data : \n");
	obj.pre_order(obj.root);
	process.stdout.write("\nPost-order Data : \n");
	obj.post_order(obj.root);
}
main();

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
/*
  Swift 4 Program
  Construct Binary Tree from a Linked List 
*/
class TreeNode {
  var data: Int;
  var left: TreeNode? ;
  var right: TreeNode? ;
 
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class LinkNode {
  var data: Int;
  var next: LinkNode? ;
  init(_ value: Int) {
    self.data = value;
    self.next = nil;
  }
}
class MyQueue {
  var element: TreeNode? ;
  var next: MyQueue? ;
  init(_ node: TreeNode? ) {
    self.element = node;
    self.next = nil;
  }
}
class BinaryTree {
  var root: TreeNode? ;
  var head: LinkNode? ;
  var front: MyQueue? ;
  var back: MyQueue? ;
  
  init() {
    self.root = nil;
    self.head = nil;
    self.front = nil;
    self.back = nil;
  }
  func insert(_ value: Int) {
    let node: LinkNode? = LinkNode(value);
    if (node == nil) {
      print("Memory overflow\n");
    } else {
      if (self.head == nil) {
        self.head = node;
      } else {
        var temp: LinkNode? = self.head;
        while (temp!.next != nil) {
          temp = temp!.next;
        }
        temp!.next = node;
      }
    }
  }
  func in_order(_ node: TreeNode? ) {
    if (node != nil) {
      self.in_order(node!.left);
      print(node!.data, terminator: "  ");
      self.in_order(node!.right);
    }
  }
  func pre_order(_ node: TreeNode? ) {
    if (node != nil) {
      print(node!.data, terminator: "  ");
      self.pre_order(node!.left);
      self.pre_order(node!.right);
    }
  }
  func post_order(_ node: TreeNode? ) {
    if (node != nil) {
      self.post_order(node!.left);
      self.post_order(node!.right);
      print(node!.data, terminator: "  ");
    }
  }
  func enqueue(_ tree_node: TreeNode? ) -> MyQueue {
    return MyQueue(tree_node);
  }
  func dequeue() {
    if (self.front != nil) {
      var remove: MyQueue? = self.front;
      self.front = remove!.next;
      remove!.element = nil;
      remove!.next = nil;
      remove = nil;
    }
  }
  func construct() {
    if (self.head == nil) {
      return;
    }
    self.root = TreeNode(self.head!.data);
    var new_node: TreeNode? = nil;
    self.front = self.enqueue(self.root);
    self.back = self.front;
    self.head = self.head!.next;
    while (self.head != nil) {
      new_node = TreeNode(self.head!.data);
      self.front!.element!.left = new_node;
      self.back!.next = self.enqueue(new_node);
      self.back = self.back!.next;
      if (self.head!.next != nil) {
        new_node = TreeNode(self.head!.next!.data);
        self.front!.element!.right = new_node;
        self.back!.next = self.enqueue(new_node);
        self.back = self.back!.next;
        self.head = self.head!.next;
      }
      self.head = self.head!.next;
      self.dequeue();
    }
  }
}
func main() {
  let obj: BinaryTree = BinaryTree();
  /*
           1
         /   \
        2     3
       / \   / \
      4   5 6   7
     /
    8   
  */
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  obj.insert(7);
  obj.insert(8);
  obj.construct();
  print("\nIn-order Data : ");
  obj.in_order(obj.root);
  print("\nPre-order Data : ");
  obj.pre_order(obj.root);
  print("\nPost-order Data : ");
  obj.post_order(obj.root);
}
main();

Output

Preorder :
  1  2  4  8  5  3  6  7
Inorder :
  8  4  2  5  1  6  3  7
Postorder :
  8  4  5  2  6  7  3  1
Last updated on by Kalkicode




Comment

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