fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. /**
  4.  * Find median at a given Level in a Binary Tree
  5.  * @author Prateek
  6.  */
  7. class MedianAtLevelK {
  8.  
  9. 	/**
  10. 	 * Subroutine to calculate median
  11. 	 * @param level : Given level
  12. 	 * @return : median
  13. 	 */
  14. 	public Node medianAtLevelK(Node root, int level){
  15. 		List<Node> list = itemsAtLevelK(root,level,new ArrayList<Node>());
  16. 		Node median = list.get(list.size()/2);
  17. 		System.out.println("Available Nodes @ given Level : " + list);
  18. 		System.out.println("Median : " +median);
  19. 		return median;
  20. 	}
  21.  
  22. 	/**
  23. 	 * Fills the list with items at given level
  24. 	 * @return
  25. 	 */
  26. 	public List<Node> itemsAtLevelK(Node root,int level, List<Node> list){
  27. 		if(root == null)
  28. 			return list;
  29.  
  30. 		if(level == 1)
  31. 			list.add(root);
  32.  
  33. 		list=itemsAtLevelK(root.left, level-1,list);
  34. 		list=itemsAtLevelK(root.right, level-1,list);
  35.  
  36. 		return list;
  37. 	}
  38.  
  39. 	public static void main(String[] args) {
  40. 		/*Node root = new Node(1) ;
  41. 		root.left= new Node(2) ;
  42. 		root.right= new Node(3) ;
  43. 		root.left.left= new Node(4) ;
  44. 		root.left.right= new Node(5) ;  	
  45. 		root.right.left= new Node(6) ;
  46. 		root.right.right= new Node(7) ;  
  47. 		root.left.right.left= new Node(8) ;  
  48. 		root.left.right.right= new Node(9) ;
  49. 		root.left.right.left.right= new Node(10) ;  */
  50.  
  51. 		Node root = new Node(1) ;
  52. 		root.left= new Node(2) ;
  53. 		root.right= new Node(3) ;
  54. 		root.left.left= new Node(4) ;
  55. 		root.left.right= new Node(5) ;  	
  56. 		root.right.left= new Node(6) ;
  57. 		root.right.right= new Node(7) ; 
  58.  
  59.  
  60. 		root.left.left.right= new Node(8) ;  
  61. 		root.left.left.right.left= new Node(9) ;
  62.  
  63. 		MedianAtLevelK obj= new MedianAtLevelK();
  64. 		obj.medianAtLevelK(root,3);
  65. 	}
  66. }
  67. class Node {
  68. 	public Node left;
  69. 	public int data;
  70. 	public Node right;
  71.  
  72. 	public Node(int val)	{
  73. 		this.data=val;
  74. 	}
  75.  
  76. 	@Override
  77. 	public String toString(){
  78. 		return this.data + "";
  79. 	}
  80. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Available Nodes @ given Level : [4, 5, 6, 7]
Median : 6
https://ideone.com/nWFJYY
Median at a given Level in binary Tree
language:
Java (12.0.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!