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