java how to draw a recursive tree
Construct a Binary Tree in Level Order using Recursion
Given an array of integers, the task is to construct a binary tree in level order fashion using Recursion.
Examples
Given an array arr[] = {15, 10, 20, 8, 12, 16, 25}
Approach:
Idea is to keep track of the number of child nodes in the left sub-tree and right sub-tree and then take the decision on the basis of these counts.
- When the count of children nodes in left and right sub-tree are equal, then the node has to be inserted in left sub-tree by creating a new level in the binary tree.
- When the count of children nodes in the left sub-tree is greater than the count of the children nodes in the right sub-tree then there are two cases.
- When the left sub-tree is perfect binary tree, then node is to be inserted in right sub-tree.
- When left sub-tree is not perfect binary tree, then node is to be inserted in left sub-tree.
A perfect binary tree with n levels have 2(n-1) nodes with all the leaf nodes at same level.
Below is the implementation of the above approach
C++
#include <iostream>
using namespace std;
struct Node {
int data;
int rcount;
int lcount;
struct Node* left;
struct Node* right;
};
bool isPBT( int count)
{
count = count + 1;
while (count % 2 == 0)
count = count / 2;
if (count == 1)
return true ;
else
return false ;
}
struct Node* newNode( int data)
{
struct Node* temp =
( struct Node*) malloc (
sizeof ( struct Node)
);
temp->data = data;
temp->right = NULL;
temp->left = NULL;
temp->rcount = 0;
temp->lcount = 0;
}
struct Node* insert( struct Node* root,
int data)
{
if (root == NULL) {
struct Node* n = newNode(data);
return n;
}
if (root->rcount == root->lcount) {
root->left = insert(root->left, data);
root->lcount += 1;
}
else if (root->rcount < root->lcount) {
if (isPBT(root->lcount)) {
root->right = insert(root->right, data);
root->rcount += 1;
}
else {
root->left = insert(root->left, data);
root->lcount += 1;
}
}
return root;
}
void inorder( struct Node* root)
{
if (root != NULL) {
inorder(root->left);
cout << root->data << " " ;
inorder(root->right);
}
}
int main()
{
int arr[] = { 8, 6, 7, 12, 5, 1, 9 };
int size = sizeof (arr) / sizeof ( int );
struct Node* root = NULL;
for ( int i = 0; i < size; i++)
root = insert(root, arr[i]);
inorder(root);
return 0;
}
Java
class Node {
int data;
int rcount;
int lcount;
Node left;
Node right;
Node( int data)
{
this .data = data;
this .rcount = this .lcount = 0 ;
this .left = this .right = null ;
}
static void inorder(Node root)
{
if (root != null ) {
inorder(root.left);
System.out.print(root.data + " " );
inorder(root.right);
}
}
static boolean isPBT( int count)
{
count = count + 1 ;
while (count % 2 == 0 )
count = count / 2 ;
if (count == 1 )
return true ;
else
return false ;
}
static Node insert(Node root, int data)
{
if (root == null ) {
Node n = new Node(data);
return n;
}
if (root.rcount == root.lcount) {
root.left = insert(root.left, data);
root.lcount += 1 ;
}
else if (root.rcount < root.lcount) {
if (isPBT(root.lcount)) {
root.right = insert(root.right, data);
root.rcount += 1 ;
}
else {
root.left = insert(root.left, data);
root.lcount += 1 ;
}
}
return root;
}
public static void main(String args[])
{
int arr[] = { 8 , 6 , 7 , 12 , 5 , 1 , 9 };
int size = 7 ;
Node root = null ;
for ( int i = 0 ; i < size; i++)
root = insert(root, arr[i]);
inorder(root);
}
}
Python3
class Node:
def __init__( self , data):
self .data = data
self .rcount = 0
self .lcount = 0
self .left = None
self .right = None
def isPBT(count: int ) - > bool :
count = count + 1
while (count % 2 = = 0 ):
count = count / 2
if (count = = 1 ):
return True
else :
return False
def insert(root: Node, data: int ) - > Node:
if (root is None ):
n = Node(data)
return n
if (root.rcount = = root.lcount):
root.left = insert(root.left, data)
root.lcount + = 1
elif (root.rcount < root.lcount):
if (isPBT(root.lcount)):
root.right = insert(root.right, data)
root.rcount + = 1
else :
root.left = insert(root.left, data)
root.lcount + = 1
return root
def inorder(root: Node) - > None :
if root ! = None :
inorder(root.left)
print (root.data, end = " " )
inorder(root.right)
if __name__ = = "__main__" :
arr = [ 8 , 6 , 7 , 12 , 5 , 1 , 9 ]
size = len (arr)
root = None
for i in range (size):
root = insert(root, arr[i])
inorder(root)
C#
using System;
class Node {
public int data;
public int rcount;
public int lcount;
public Node left;
public Node right;
public Node( int data)
{
this .data = data;
this .rcount = this .lcount = 0;
this .left = this .right = null ;
}
static void inorder(Node root)
{
if (root != null ) {
inorder(root.left);
Console.Write(root.data + " " );
inorder(root.right);
}
}
static bool isPBT( int count)
{
count = count + 1;
while (count % 2 == 0)
count = count / 2;
if (count == 1)
return true ;
else
return false ;
}
static Node insert(Node root, int data)
{
if (root == null ) {
Node n = new Node(data);
return n;
}
if (root.rcount == root.lcount) {
root.left = insert(root.left, data);
root.lcount += 1;
}
else if (root.rcount < root.lcount) {
if (isPBT(root.lcount)) {
root.right = insert(root.right, data);
root.rcount += 1;
}
else {
root.left = insert(root.left, data);
root.lcount += 1;
}
}
return root;
}
public static void Main(String []args)
{
int []arr = { 8, 6, 7, 12, 5, 1, 9 };
int size = 7;
Node root = null ;
for ( int i = 0; i < size; i++)
root = insert(root, arr[i]);
inorder(root);
}
}
Javascript
<script>
class Node{
constructor(data){
this .data = data
this .rcount = 0
this .lcount = 0
this .left = null
this .right = null
}
}
function isPBT(count){
count = count + 1
while (count % 2 == 0)
count = count / 2
if (count == 1)
return true
else
return false
}
function insert(root, data){
if (!root){
let n = new Node(data)
return n
}
if (root.rcount == root.lcount){
root.left = insert(root.left, data)
root.lcount += 1
}
else if (root.rcount < root.lcount){
if (isPBT(root.lcount)){
root.right = insert(root.right, data)
root.rcount += 1
}
else {
root.left = insert(root.left, data)
root.lcount += 1
}
}
return root
}
function inorder(root){
if (root){
inorder(root.left)
document.write(root.data, " " )
inorder(root.right)
}
}
let arr = [ 8, 6, 7, 12, 5, 1, 9 ]
let size = arr.length
let root = null
for (let i=0;i<size;i++)
root = insert(root, arr[i])
inorder(root)
</script>
Time Complexity: O(N*logN), where N is the size of the given array.
Auxiliary Space: O(N), for creating N nodes.
Source: https://www.geeksforgeeks.org/construct-a-binary-in-level-order-using-recursion/
0 Response to "java how to draw a recursive tree"
Publicar un comentario