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 AncestorDiameter of a Binary search tree
LEVEL:Beginner
Description
Given a array of integers convert them to binary search tree and find the diameter of the tree
Input Format
First line contains n indicating no of elements in the array Next line contains n integers representing the elements of the array
Output Format
Print the diameter of the binary search tree formed
5 2 2 5 4 8
4
8 2 5 4 6 8 1 3 5
5
10 10 10 10 2 4 5 6 8 3 20
9
Login to see Discussion
Approach
Step-i) Create a class Node with instances data of int type and left,right of Node type
Step-ii)create a default constructor which initializes left and right to null
Step-iii)create a constructor which accepts key as argument and assigns it to data
(this class is used to create a node of the tree)
Step-iv)create another class binary tree
Step-v)create a public method which return Node and takes root,node of Node type as arguments
Step-vi)if root is null assign node to root and return node
Step-vii)if data of root is less than data of node go to next step else go to ix
Step-viii)if right of root is null assign node to root right else call the insert method passing root.right and node as argument
Step-ix)if left of root is null assign node to root left else call the insert method passing root.left and node as argument
Step-x)return root
(now we are done with the insert method)
Step-xi)now create a method height which return height and takes node of Node type as argument;
Step-xii)if node equal to null return 0 else return 1+ max of height of node left and height of node right
(we are completed with height method)
Step-xiii)create a class Height with only one instance h
Step-xiv)create a method diameter_tree which accepts root of Node type and height of type Height and return int
Step-xv)create two instances of class Height naming lh and rh
Step-xvi)if root is equal to null assign 0 to height.h and return 0
Step-xvii)call the function diameter_tree passing root.left and lh and store the result in ldiameter
Step-xviii)call the function diameter_tree passing root.right and rh and store the result in rdiameter
Step-xix)return max of lh.h+rh.h+1 and max of ldiameter and rdiameter
(now we are done with this method)
Step-xx)create another method diameter which accepts root as argument and returns int
Step-xxi)create instance of class Height
Step-xxii)return the result of diameter_tree passing root and instance of class Height as argument
(we are done with this method)
Step-xxiii)in main method take the input n which tells the no of inputs in the array
Step-xxiv)read the array elements
Step-xxv)traverse the array and pass the elements to the binary search insert function to construct the binary search tree
Step-xxvi)call the diameter method passing root as argument
Step-xxvii)print the result
Time Complexity: O(n)
Space Complexity: O(1)
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