Beginner
1. Binary Search2. Linear Search3. Fibonacci Search4. Bubble Sort5. Insertion Sort6. Selection Sort7. Quick Sort8. Merge Sort9. Addition of two matrixes10. Subtraction of two matrixes11. Multiplication of two matrixes12. Transpose of given Matrix13. EUCLIDIAN GCD ALGORITHM14. Fabinocci Numbers with matrix multiplication15. Fast Exponential16. Modular inversion17. Prime seiving18. Heap(using array)19. Heapify20. Heap Sort21. Linear Probing22. Open Addressing23. Collision Avoidance24. Binary Search Tree Traversal Techniques25. Finding Kth Largest Element in Binary Tree26. Diameter of a Binary search tree27. Depth of Binary Tree28. Number of Nodes in BST29. Convert Array to Binary Tree30. Convert Array to General Tree31. Lowest Common AncestorConvert Array to General Tree
LEVEL:Beginner
Description
Convert the given array to the K ary tree.
Input Format
First line contains N representing no of elements in the array Next line contains N separated integers which are the array elements Next line contains K determines no of nodes that a root should have.
Output Format
Convert the array to M-ary and print the post order fashion of it.
10 1 2 5 6 7 3 8 9 10 4 3
5 6 7 2 8 9 10 3 4 1
5 1 2 3 4 5 2
3 4 2 5 1
10 1 8 2 4 9 25 4 7 2 5 5
2 4 9 25 4 8 2 5 7 1
Login to see Discussion
Approach
Step-i) create a static class Node which has key of int type and child of Vector with int type
Step-ii)create a method newNode which return Node and accepts int as argument
Step-iii)create node of Node type
Step-iv)initialize key to value and child to vector type and return the node
Step-v)create a static variable ind
Step-vi)create a M_ary_Tree method which accepts a array, and four int values as argument and return Node
Step-vii)if n is less than or equal to 0 return null
Step-viii)create node of Node type and assign key to the value of arr[ind]
Step-ix)if node is null print "Memory Error" and return null
Step-x)initialize i to 0
Step-xi)if ind is less than n and h is greater than 1 increment ind by one and add the value of
M_ary_Tree(arr,n,k,h-1) to child of node
Step-xii)else just add null to child of node
Step-xiii)increment i by one value and repeat steps xi to xiii till i is less than k
Step-(now we are completed with the above method)
Step-xiv)create a method Build_M_Tree which takes arr,n,k,in as argument and returns a Node
Step-xv)calculate the value of (int)Math.ceil(Math.log((double)n(k - 1) + 1) /Math.log((double)k)) and assign it to height
Step-xvi)assign in to ind
Step-xvii)return the value of M_ary_Tree(arr, n, k, height)
Step-(we are completed with Build_M_Tree method)
Step-xviii)create a post order method which takes root and k as argument
Step-xix)if root equals to null just return
Step-xx)initialize i to 0
Step-xxi)call the method post order passing root.child.get(i) and k as argument
Step-xxii)increment i by one value
Step-xxiii)repeat steps xxi and xxii till i is less than k
Step-xxiv)print the value of root.key
Step-xxv)in main method read n, array,k and assign 0 to ind
Step-xxvi)then call the Build_M_tree passing arr,n,k,ind as argument
Step-xxvii)print the tree in the post order fashion
Time Complexity: O(n)
Space Complexity: O(n)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution