Posted on by Kalkicode
Code Binary Tree

# 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.

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

root->left=construct(data,size,element);

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) {
} 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) {

//return current node
} 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) {

//return current node
} 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) :
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_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end

class BinaryTree
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)
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) {
} 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) {
} 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) {
} 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``````

## 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.

Categories
Relative Post