Skip to main content

Construct Binary Tree from given parent array

In this article, we will learn how to construct a binary tree from a given parent array. The parent array contains the parent node of each node in the tree, except for the root node, which has no parent.

Constructing Binary Tree using given parent array

The parent array contains n integers, where the value at index i represents the parent of the node at index i in the binary tree.

Code Solution

/*
  C Program 
+ Construct Binary Tree from given parent array
*/
#include<stdio.h>
#include<stdlib.h>

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


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;
}

//Display tree element preorder form
void preOrderData(struct Node* 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 Node* 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 Node* node){

    if(node!=NULL)
    {
      
      postOrderData(node->left);

      postOrderData(node->right);

      //Print node value
      printf("%3d",node->data);
    }
}
int getIndex(int data[],int size,int value)
{
  if(size<=1) return -1;
  int index=-1;
  for (int i = 0; i < size; ++i)
  {
    if (data[i] == value)
    {
      index=i;
      data[i]=-2;
      break;
    }
  }
  return index;
}
//Construct binary tree using given array
struct Node* construct(int data[],int size ,int element)
{
  if(element>=size) return NULL;
  //get the element index
  element = getIndex(data,size,element);
  
  if(element!=-1)
  {
     
    struct Node*root=insert(element); 
    
    //add left child
    root->left=construct(data,size,element); 
    
    //add right child
    root->right=construct(data,size,element);

    //return current node
    return root;
  }
  else
  {
    return NULL;
  }

}
int main(){
  //parent array
  int data[]={3,7,7,4,8,6,4,8,-1,1}; 

  int size = sizeof(data) / sizeof(data[0]);
  /*
           8
        /    \
       4      7
      / \    / \
     3   6  1   2
    /    /   \
   0    5     9


  */
  struct Node*root=construct(data,size,-1); 

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

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

Output

Preorder :
  8  4  3  0  6  5  7  1  9  2
Inorder :
  0  3  4  5  6  8  9  1  7  2
Postorder :
  0  3  5  6  4  9  1  2  7  8
/*
C++ Program 
Construct Binary Tree from given parent array
*/
#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left, *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinaryTree {
  public:
  Node *root;
  BinaryTree() {
    this->root = NULL;
  }
  void preOrderData(Node *node) {
    if (node != NULL) {
      cout << node->data << "  ";
      this->preOrderData(node->left);
      this->preOrderData(node->right);
    }
  }
  void inOrderData(Node *node) {
    if (node != NULL) {
      this->inOrderData(node->left);
      cout << node->data << "  ";
      this->inOrderData(node->right);
    }
  }
  void postOrderData(Node *node) {
    if (node != NULL) {
      this->postOrderData(node->left);
      this->postOrderData(node->right);
      cout << node->data << "  ";
    }
  }
  int getIndex(int arr[], int size, int value) {
    if (size <= 1) {
      return -1;
    }
    int index = -1, i = 0;
    while (i < size) {
      if (arr[i] == value) {
        index = i;
        arr[i] = -2;
        break;;
      }
      i++;
    }
    return index;
  }
  Node *construct(int arr[], int size, int element) {
    if (element >= size) {
      return NULL;
    }
    element = this->getIndex(arr, size, element);
    if (element != -1) {
      Node *head = new Node(element);
      head->left = this->construct(arr, size, element);
      head->right = this->construct(arr, size, element);
      return head;
    } else {
      return NULL;
    }
  }
};

int main() {
  BinaryTree obj;
  int arr[] = { 3, 7, 7, 4, 8, 6, 4, 8, -1, 1};
  int size = sizeof(arr)/sizeof(arr[0]);
  obj.root = obj.construct(arr, size, -1);
  /*
          8
        /    \
       4      7
      / \    / \
     3   6  1   2
    /    /   \
   0    5     9


  */

  cout << "Preorder :\n";
  obj.preOrderData(obj.root);
  cout << "\nInorder :\n";
  obj.inOrderData(obj.root);
  cout << "\nPostorder :\n";
  obj.postOrderData(obj.root);

  return 0;
}

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
/*
Java Program 
Construct Binary Tree from given parent array
*/

//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 = null;
    right = null;
  }
}

public class BinaryTree {

  public Node root;

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



  //Display tree element preorder form
  public void preOrderData(Node node) {

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

      preOrderData(node.right);
    }
  }

  //Display tree element In OrderData form
  public void inOrderData(Node node) {

    if (node != null) {

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

  //Display tree element In Post order form
  public void postOrderData(Node node) {

    if (node != null) {

      postOrderData(node.left);

      postOrderData(node.right);

      //Print node value
      System.out.print( node.data+"  ");
    }
  }
  public int getIndex(int[] arr, int size, int value) {
    if (size <= 1) {
      return -1;
    }
    int index = -1, i = 0;
    while (i < size) {
      if (arr[i] == value) {
        index = i;
        arr[i] = -2;
        break;
      }
      i++;
    }
    return index;
  }
  //Construct binary tree using given array
  public Node construct(int[] arr, int size, int element) {
    if (element >= size) {
      return null;
    }
    //get the element index
    element = getIndex(arr, size, element);

    if (element != -1) {

      Node head = new Node(element);

      //add left child
      head.left = construct(arr, size, element);

      //add right child
      head.right = construct(arr, size, element);

      //return current node
      return head;
    } else {
      return null;
    }

  }

  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();
    //parent array
    int[] arr = {3,7,7,4,8,6,4,8,-1,1};

    int size = arr.length;
    /*
            8
          /    \
         4      7
        / \    / \
       3   6  1   2
      /    /   \
     0    5     9


    */
    obj.root = obj.construct(arr, size, -1);

    //Display elements
    System.out.print("Preorder :\n");
    obj.preOrderData(obj.root);

    System.out.print("\nInorder :\n");
    obj.inOrderData(obj.root);

    System.out.print("\nPostorder :\n");
    obj.postOrderData(obj.root);
  }
}

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
/*
C# Program 
Construct Binary Tree from given parent array
*/
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 = null;
		right = null;
	}
}

public class BinaryTree {

	public Node root;

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



	//Display tree element preorder form
	public void preOrderData(Node node) {

		if (node != null) {
			//Print node value
			Console.Write(node.data+"  ");
			preOrderData(node.left);

			preOrderData(node.right);
		}
	}

	//Display tree element In OrderData form
	public void inOrderData(Node node) {

		if (node != null) {

			inOrderData(node.left);
			//Print node value
			Console.Write(node.data+"  ");
			inOrderData(node.right);
		}
	}

	//Display tree element In Post order form
	public void postOrderData(Node node) {

		if (node != null) {

			postOrderData(node.left);

			postOrderData(node.right);

			//Print node value
			Console.Write( node.data+"  ");
		}
	}
	public int getIndex(int[] data, int size, int value) {
		if (size <= 1) {
			return -1;
		}
		int index = -1, i = 0;
		while (i < size) {
			if (data[i] == value) {
				index = i;
				data[i] = -2;
				break;
			}
			i++;
		}
		return index;
	}
	//Construct binary tree using given array
	public Node construct(int[] data, int size, int element) {
		if (element >= size) {
			return null;
		}
		//get the element index
		element = getIndex(data, size, element);

		if (element != -1) {

			Node head = new Node(element);

			//add left child
			head.left = construct(data, size, element);

			//add right child
			head.right = construct(data, size, element);

			//return current node
			return head;
		} else {
			return null;
		}

	}

	public static void Main(String[] args) {
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		//parent array
		int[] data = {3,7,7,4,8,6,4,8,-1,1};

		int size = data.Length;
		/*
            8
          /    \
         4      7
        / \    / \
       3   6  1   2
      /    /   \
     0    5     9


    */
		obj.root = obj.construct(data, size, -1);

		//Display elements
		Console.Write("Preorder :\n");
		obj.preOrderData(obj.root);

		Console.Write("\nInorder :\n");
		obj.inOrderData(obj.root);

		Console.Write("\nPostorder :\n");
		obj.postOrderData(obj.root);
	}
}

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
# Python Program 
# Construct Binary Tree from given parent list
class Node :

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

class BinaryTree :

  def __init__(self) :
    self.root = None
  
  def preOrderData(self, node) :
    if (node != None) :
      print(node.data ,end="  ")
      self.preOrderData(node.left)
      self.preOrderData(node.right)
    
  
  def inOrderData(self, node) :
    if (node != None) :
      self.inOrderData(node.left)
      print(node.data ,end="  ")
      self.inOrderData(node.right)
    
  
  def postOrderData(self, node) :
    if (node != None) :
      self.postOrderData(node.left)
      self.postOrderData(node.right)
      print(node.data ,end="  ")
    
  
  def getIndex(self, arr, size, value) :
    if (size <= 1) :
      return -1
    
    index = -1
    i = 0
    while (i < size) :
      if (arr[i] == value) :
        index = i
        arr[i] = -2
        break
      
      i += 1
    
    return index
  
  def construct(self, arr, size, element) :
    if (element >= size) :
      return None
    
    element = self.getIndex(arr, size, element)
    if (element != -1) :
      head = Node(element)
      head.left = self.construct(arr, size, element)
      head.right = self.construct(arr, size, element)
      return head
    else :
      return None
    
  
def main() :
  obj = BinaryTree()
  arr = [3, 7, 7, 4, 8, 6, 4, 8, -1, 1]
  size = len(arr)
  obj.root = obj.construct(arr, size, -1)
  #
  #            8
  #          /    \
  #         4      7
  #        / \    / \
  #       3   6  1   2
  #      /    /   \
  #     0    5     9
  #    
  print("Preorder :")
  obj.preOrderData(obj.root)
  print("\nInorder :")
  obj.inOrderData(obj.root)
  print("\nPostorder :")
  obj.postOrderData(obj.root)
  

if __name__ == "__main__":
  main()

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
# Ruby Program
# Construct Binary Tree from given parent array
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 preOrderData(node) 
		if (node != nil) 
			print(node.data ,"  ")
			self.preOrderData(node.left)
			self.preOrderData(node.right)
		end
	end
	def inOrderData(node) 
		if (node != nil) 
			self.inOrderData(node.left)
			print(node.data ,"  ")
			self.inOrderData(node.right)
		end
	end
	def postOrderData(node) 
		if (node != nil) 
			self.postOrderData(node.left)
			self.postOrderData(node.right)
			print(node.data ,"  ")
		end
	end
	def getIndex(arr, size, value) 
		if (size <= 1) 
			return -1
		end
		index = -1
		i = 0
		while (i < size) 
			if (arr[i] == value) 
				index = i
				arr[i] = -2
				break
			end
			i += 1
		end
		return index
	end
	def construct(arr, size, element) 
		if (element >= size) 
			return nil
		end
		element = self.getIndex(arr, size, element)
		if (element != -1) 
			head = Node.new(element)
			head.left = self.construct(arr, size, element)
			head.right = self.construct(arr, size, element)
			return head
		else 
			return nil
		end
	end
end

def main() 
	obj = BinaryTree.new()
	arr = [3, 7, 7, 4, 8, 6, 4, 8, -1, 1]
	size = arr.length
	obj.root = obj.construct(arr, size, -1)
	#
	#            8
	#          /    \
	#         4      7
	#        / \    / \
	#       3   6  1   2
	#      /    /   \
	#     0    5     9
	#    
	print("Preorder  :\n")
	obj.preOrderData(obj.root)
	print("\nInorder  :\n")
	obj.inOrderData(obj.root)
	print("\nPostorder  :\n")
	obj.postOrderData(obj.root)
end
main()

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
<?php
/*
  Php Program
  Construct Binary Tree from given parent array
*/
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 preOrderData($node) {
    if ($node != null) {
      echo ($node->data ."  ");
      $this->preOrderData($node->left);
      $this->preOrderData($node->right);
    }
  }
  public  function inOrderData($node) {
    if ($node != null) {
      $this->inOrderData($node->left);
      echo ($node->data ."  ");
      $this->inOrderData($node->right);
    }
  }
  public  function postOrderData($node) {
    if ($node != null) {
      $this->postOrderData($node->left);
      $this->postOrderData($node->right);
      echo ($node->data ."  ");
    }
  }
  public  function getIndex(&$arr, $size, $value) {
    if ($size <= 1) {
      return -1;
    }
    $index = -1;
    $i = 0;
    while ($i < $size) {
      if ($arr[$i] == $value) {
        $index = $i;
        $arr[$i] = -2;
        break;;
      }
      $i++;
    }
    return $index;
  }
  public  function construct(&$arr, $size, $element) {
    if ($element >= $size) {
      return null;
    }
    $element = $this->getIndex($arr, $size, $element);
    if ($element != -1) {
      $head = new Node($element);
      $head->left = $this->construct($arr, $size, $element);
      $head->right = $this->construct($arr, $size, $element);
      return $head;
    } else {
      return null;
    }
  }
}

function main() {
  $obj = new BinaryTree();
  $arr = array(3, 7, 7, 4, 8, 6, 4, 8, -1, 1);
  $size = count($arr) ;
  $obj->root =
  $obj->construct($arr, $size, -1);
  /*
          8
        /    \
       4      7
      / \    / \
     3   6  1   2
    /    /   \
   0    5     9


  */
  echo("Preorder :\n");
  $obj->preOrderData($obj->root);
  echo("\nInorder :\n");
  $obj->inOrderData($obj->root);
  echo("\nPostorder :\n");
  $obj->postOrderData($obj->root);
}

main();

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
/*
  Node JS Program
  Construct Binary Tree from given parent array
*/
class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree {
	
	constructor() {
		this.root = null;
	}
	preOrderData(node) {
		if (node != null) {
			process.stdout.write(node.data + "  ");
			this.preOrderData(node.left);
			this.preOrderData(node.right);
		}
	}
	inOrderData(node) {
		if (node != null) {
			this.inOrderData(node.left);
			process.stdout.write(node.data + "  ");
			this.inOrderData(node.right);
		}
	}
	postOrderData(node) {
		if (node != null) {
			this.postOrderData(node.left);
			this.postOrderData(node.right);
			process.stdout.write(node.data + "  ");
		}
	}
	getIndex(arr, size, value) {
		if (size <= 1) {
			return -1;
		}
		var index = -1;
		var i = 0;
		while (i < size) {
			if (arr[i] == value) {
				index = i;
				arr[i] = -2;
				break;;
			}
			i++;
		}
		return index;
	}
	construct(arr, size, element) {
		if (element >= size) {
			return null;
		}
		element = this.getIndex(arr, size, element);
		if (element != -1) {
			var head = new Node(element);
			head.left = this.construct(arr, size, element);
			head.right = this.construct(arr, size, element);
			return head;
		} else {
			return null;
		}
	}
}

function main() {
	var obj = new BinaryTree();
	var arr = [3, 7, 7, 4, 8, 6, 4, 8, -1, 1];
	var size = arr.length;
	obj.root = obj.construct(arr, size, -1);
	/*
            8
          /    \
         4      7
        / \    / \
       3   6  1   2
      /    /   \
     0    5     9


    */
	process.stdout.write("Preorder :\n");
	obj.preOrderData(obj.root);
	process.stdout.write("\nInorder :\n");
	obj.inOrderData(obj.root);
	process.stdout.write("\nPostorder :\n");
	obj.postOrderData(obj.root);
}

main();

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
/*
  Swift 4 Program
  Construct Binary Tree from given parent array
*/
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 preOrderData(_ node: Node? ) {
    if (node != nil) {
      print(node!.data ,terminator:"  ");
      self.preOrderData(node!.left);
      self.preOrderData(node!.right);
    }
  }
  func inOrderData(_ node: Node? ) {
    if (node != nil) {
      self.inOrderData(node!.left);
      print(node!.data ,terminator:"  ");
      self.inOrderData(node!.right);
    }
  }
  func postOrderData(_ node: Node? ) {
    if (node != nil) {
      self.postOrderData(node!.left);
      self.postOrderData(node!.right);
      print(node!.data ,terminator:"  ");
    }
  }
  func getIndex(_ arr: inout [Int] , _ size : Int, _ value: Int) -> Int {
    if (size <= 1) {
      return -1;
    }
    var index: Int = -1;
    var i = 0;
    while (i < size) {
      if (arr[i] == value) {
        index = i;
        arr[i] = -2;
        break;
      }
      i += 1;
    }
    return index;
  }
  func construct(_ arr: inout [Int] , _ size : Int, _ element: Int) -> Node? {
    if (element >= size) {
      return nil;
    }
    let location = self.getIndex(&arr, size, element);
    if (location != -1) {
      let head: Node? = Node(location);
      head!.left = self.construct(&arr, size, location);
      head!.right = self.construct(&arr, size, location);
      return head;
    } else {
      return nil;
    }
  }
}

func main() {
  let obj: BinaryTree = BinaryTree();
  var arr: [Int] = [3, 7, 7, 4, 8, 6, 4, 8, -1, 1];
  let size: Int = arr.count;
  obj.root = obj.construct(&arr, size, -1);

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


  */
  print("Preorder :");
  obj.preOrderData(obj.root);
  print("\nInorder :");
  obj.inOrderData(obj.root);
  print("\nPostorder :");
  obj.postOrderData(obj.root);
}
main();

Output

Preorder :
8  4  3  0  6  5  7  1  9  2  
Inorder :
0  3  4  5  6  8  9  1  7  2  
Postorder :
0  3  5  6  4  9  1  2  7  8
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