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++
// C++ implementation to construct // Binary Tree in level order fashion #include <iostream> using namespace std; // Structure of the Node of Binary tree // with count of Children nodes in // left sub-tree and right sub-tree. struct Node { int data; int rcount; int lcount; struct Node* left; struct Node* right; }; // Function to check whether the given // Binary tree is a perfect binary tree // using the no. of nodes in tree. bool isPBT( int count) { count = count + 1; // Loop to check the count is in // the form of 2^(n-1) while (count % 2 == 0) count = count / 2; if (count == 1) return true ; else return false ; } // Function to create a new Node 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; } // Recursive function to insert // elements in a binary tree struct Node* insert( struct Node* root, int data) { // Condition when root is NULL if (root == NULL) { struct Node* n = newNode(data); return n; } // Condition when count of left sub-tree // nodes is equal to the count // of right sub-tree nodes if (root->rcount == root->lcount) { root->left = insert(root->left, data); root->lcount += 1; } // Condition when count of left sub-tree // nodes is greater than // the right sub-tree nodes else if (root->rcount < root->lcount) { // Condition when left Sub-tree is // Perfect Binary Tree then Insert // in right sub-tree. if (isPBT(root->lcount)) { root->right = insert(root->right, data); root->rcount += 1; } // If Left Sub-tree is not Perfect // Binary Tree then Insert in left sub-tree else { root->left = insert(root->left, data); root->lcount += 1; } } return root; } // Function for inorder Traversal of tree. void inorder( struct Node* root) { if (root != NULL) { inorder(root->left); cout << root->data << " " ; inorder(root->right); } } // Driver Code int main() { int arr[] = { 8, 6, 7, 12, 5, 1, 9 }; int size = sizeof (arr) / sizeof ( int ); struct Node* root = NULL; // Loop to insert nodes in // Binary Tree in level order for ( int i = 0; i < size; i++) root = insert(root, arr[i]); inorder(root); return 0; } |
Java
// Java implementation to construct // Binary Tree in level order fashion 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 ; } // Function for inorder Traversal of tree. static void inorder(Node root) { if (root != null ) { inorder(root.left); System.out.print(root.data + " " ); inorder(root.right); } } // Function to check whether the given // Binary tree is a perfect binary tree // using the no. of nodes in tree. static boolean isPBT( int count) { count = count + 1 ; // Loop to check the count is in // the form of 2^(n-1) while (count % 2 == 0 ) count = count / 2 ; if (count == 1 ) return true ; else return false ; } // Recursive function to insert // elements in a binary tree static Node insert(Node root, int data) { // Condition when root is NULL if (root == null ) { Node n = new Node(data); return n; } // Condition when count of left sub-tree // nodes is equal to the count // of right sub-tree nodes if (root.rcount == root.lcount) { root.left = insert(root.left, data); root.lcount += 1 ; } // Condition when count of left sub-tree // nodes is greater than // the right sub-tree nodes else if (root.rcount < root.lcount) { // Condition when left Sub-tree is // Perfect Binary Tree then Insert // in right sub-tree. if (isPBT(root.lcount)) { root.right = insert(root.right, data); root.rcount += 1 ; } // If Left Sub-tree is not Perfect // Binary Tree then Insert in left sub-tree else { root.left = insert(root.left, data); root.lcount += 1 ; } } return root; } // Driver Code public static void main(String args[]) { int arr[] = { 8 , 6 , 7 , 12 , 5 , 1 , 9 }; int size = 7 ; Node root = null ; // Loop to insert nodes in // Binary Tree in level order Traversal for ( int i = 0 ; i < size; i++) root = insert(root, arr[i]); inorder(root); } } |
Python3
# Python3 implementation to construct # Binary Tree in level order fashion # Structure of the Node of Binary tree # with count of Children nodes in # left sub-tree and right sub-tree. class Node: def __init__( self , data): self .data = data self .rcount = 0 self .lcount = 0 self .left = None self .right = None # Function to check whether the given # Binary tree is a perfect binary tree # using the no. of nodes in tree. def isPBT(count: int ) - > bool : count = count + 1 # Loop to check the count is in # the form of 2^(n-1) while (count % 2 = = 0 ): count = count / 2 if (count = = 1 ): return True else : return False # Recursive function to insert # elements in a binary tree def insert(root: Node, data: int ) - > Node: # Condition when root is NULL if (root is None ): n = Node(data) return n # Condition when count of left sub-tree # nodes is equal to the count # of right sub-tree nodes if (root.rcount = = root.lcount): root.left = insert(root.left, data) root.lcount + = 1 # Condition when count of left sub-tree # nodes is greater than # the right sub-tree nodes elif (root.rcount < root.lcount): # Condition when left Sub-tree is # Perfect Binary Tree then Insert # in right sub-tree. if (isPBT(root.lcount)): root.right = insert(root.right, data) root.rcount + = 1 # If Left Sub-tree is not Perfect # Binary Tree then Insert in left sub-tree else : root.left = insert(root.left, data) root.lcount + = 1 return root # Function for inorder Traversal of tree. def inorder(root: Node) - > None : if root ! = None : inorder(root.left) print (root.data, end = " " ) inorder(root.right) # Driver Code if __name__ = = "__main__" : arr = [ 8 , 6 , 7 , 12 , 5 , 1 , 9 ] size = len (arr) root = None # Loop to insert nodes in # Binary Tree in level order for i in range (size): root = insert(root, arr[i]) inorder(root) # This code is contributed by sanjeev2552 |
C#
// C# implementation to construct // Binary Tree in level order fashion 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 ; } // Function for inorder Traversal of tree. static void inorder(Node root) { if (root != null ) { inorder(root.left); Console.Write(root.data + " " ); inorder(root.right); } } // Function to check whether the given // Binary tree is a perfect binary tree // using the no. of nodes in tree. static bool isPBT( int count) { count = count + 1; // Loop to check the count is in // the form of 2^(n-1) while (count % 2 == 0) count = count / 2; if (count == 1) return true ; else return false ; } // Recursive function to insert // elements in a binary tree static Node insert(Node root, int data) { // Condition when root is NULL if (root == null ) { Node n = new Node(data); return n; } // Condition when count of left sub-tree // nodes is equal to the count // of right sub-tree nodes if (root.rcount == root.lcount) { root.left = insert(root.left, data); root.lcount += 1; } // Condition when count of left sub-tree // nodes is greater than // the right sub-tree nodes else if (root.rcount < root.lcount) { // Condition when left Sub-tree is // Perfect Binary Tree then Insert // in right sub-tree. if (isPBT(root.lcount)) { root.right = insert(root.right, data); root.rcount += 1; } // If Left Sub-tree is not Perfect // Binary Tree then Insert in left sub-tree else { root.left = insert(root.left, data); root.lcount += 1; } } return root; } // Driver Code public static void Main(String []args) { int []arr = { 8, 6, 7, 12, 5, 1, 9 }; int size = 7; Node root = null ; // Loop to insert nodes in // Binary Tree in level order Traversal for ( int i = 0; i < size; i++) root = insert(root, arr[i]); inorder(root); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation to construct // Binary Tree in level order fashion // Structure of the Node of Binary tree // with count of Children nodes in // left sub-tree and right sub-tree. class Node{ constructor(data){ this .data = data this .rcount = 0 this .lcount = 0 this .left = null this .right = null } } // Function to check whether the given // Binary tree is a perfect binary tree // using the no. of nodes in tree. function isPBT(count){ count = count + 1 // Loop to check the count is in // the form of 2^(n-1) while (count % 2 == 0) count = count / 2 if (count == 1) return true else return false } // Recursive function to insert // elements in a binary tree function insert(root, data){ // Condition when root is NULL if (!root){ let n = new Node(data) return n } // Condition when count of left sub-tree // nodes is equal to the count // of right sub-tree nodes if (root.rcount == root.lcount){ root.left = insert(root.left, data) root.lcount += 1 } // Condition when count of left sub-tree // nodes is greater than // the right sub-tree nodes else if (root.rcount < root.lcount){ // Condition when left Sub-tree is // Perfect Binary Tree then Insert // in right sub-tree. if (isPBT(root.lcount)){ root.right = insert(root.right, data) root.rcount += 1 } // If Left Sub-tree is not Perfect // Binary Tree then Insert in left sub-tree else { root.left = insert(root.left, data) root.lcount += 1 } } return root } // Function for inorder Traversal of tree. function inorder(root){ if (root){ inorder(root.left) document.write(root.data, " " ) inorder(root.right) } } // Driver Code let arr = [ 8, 6, 7, 12, 5, 1, 9 ] let size = arr.length let root = null // Loop to insert nodes in // Binary Tree in level order for (let i=0;i<size;i++) root = insert(root, arr[i]) inorder(root) // This code is contributed by shinjanpatra </script> |
Output:
12 6 5 8 1 7 9
Time Complexity: O(N*logN), where N is the size of the given array.
Auxiliary Space: O(N), for creating N nodes.
Contact Us